二叉树的递归和非递归的遍历算法模板

刷Leetcode，需要知道一定的算法模板，本次先总结下二叉树的递归和非递归的遍历算法模板。

二叉树的四种遍历方式，前中后加上层序遍历。对于二叉树的前中后层序遍历，每种遍历都可以递归和循环两种实现方法，且每种遍历的递归实现都比循环实现要简洁。下面做一个小结，看了《代码随想录》哈工大大佬的刷题指南，深受启发，因，下面代码有一定来源《代码随想录》。

递归

下面伪代码是二叉树遍历的递归算法模板，顺序是中左右，也就是前序遍历，改变中左右三行代码的顺序，前中后序三种递归遍历轻松解决。

1. defpreorderTraversal(root:TreeNode)->List[int]:
2. res=[]
3. defhelp(root):
4. ifnotroot:return
5. res.append(root.val)#中
6. help(root.left)#左
7. help(root.right)#右
8. help(root)
9. returnres

对此也提供C++代码，递归算法模板一定要加上终止条件，不然一入递归深似海，从此offer是路人，来源代码随想录。

1. voidhelp(TreeNode*root,vector<int>@amp;res){
2. if(root==nullptr){
3. return;
4. }
5. res.push_back(root->val);//中
6. help(root->left,res);//左
7. help(root->right,res);//右
8. }
9.  
10.  
11. vector<int>preorderTraversal(TreeNode*root){
12. vector<int>res;
13. help(root,res);
14. returnres;
15. }

迭代

迭代遍历二叉树的比递归难度加大，其实使用了一个栈的数据结构，《代码随想录》非常巧妙的使用空指针来作标记，原理是将处理的节点放入栈之后，紧接着放入一个空指针作为标记。

由于栈是先进后出，所以前序遍历的顺序中左右，在加到栈中，需要反过来进行添加，每添加一个元素在后面添加一个空指针，在Python中也可以使用None来代替。

下面是具体的伪代码，至于中序和后序遍历，改下向栈中添加节点的顺序即可。

1. defpreorderTraversal(root:TreeNode)->List[int]:
2. result=[]
3. st=[]
4. #1、判断root
5. ifroot:
6. st.append(root)
7. whilest:
8. node=st.pop()
9. ifnode!=None:
10. #右左中添加到栈中，然后中左右拿出
11. ifnode.right:#右
12. st.append(node.right)
13. ifnode.left:#左
14. st.append(node.left)
15. st.append(node)#中
16. #添加一个空指针记录节点
17. st.append(None)
18. else:
19. #node是空指针，那么下一个就是加入的节点
20. node=st.pop()
21. result.append(node.val)
22. returnresult

下面是具体的C++代码，由于C++中的stack中pop之后，没有返回值，因此需要额外注意。

1. vector<int>preorderTraversal(TreeNode*root){
2. vector<int>res;
3. stackst;
4. if(root!=nullptr)st.push(root);
5. while(!st.empty()){
6. TreeNode*node=st.top();
7. if(node!=nullptr){
8. st.pop();
9. if(node->right)st.push(node->right);
10. if(node->left)st.push(node->left);
11. st.push(node);
12. st.push(NULL);
13. }else{
14. //需要额外注意下
15. st.pop();
16. node=st.top();
17. st.pop();
18. res.push_back(node->val);
19. }
20. }
21. returnres;
22.  
23. }

层次遍历

其实，树的遍历也分为两种，分别是深度优先遍历和广度优先遍历。关于树的不同深度优先遍历(前序，中序和后序遍历)就是递归和非递归的写法。广度优先遍历在树中，就是层次遍历。

在二叉树的层级遍历中，我们需要用到队列这个数据结构，帮助我们完成遍历。

在Python伪代码中，

1. deflevelOrder(root:TreeNode)->List[List[int]]:
2. #1、判断root
3. ifnotroot:
4. return[]
5. #把root添加到quene中
6. quene=[root]
7. out_list=[]
8. whilequene:
9. #while第一步就是求length
10. length=len(queue)
11. in_list=[]
12. for_inrange(length):
13. #在C++中，这里需要两行
14. curnode=queue.pop(0)#（默认移除列表最后一个元素）这里需要移除队列最头上的那个
15. in_list.append(curnode.val)
16. ifcurnode.left:queue.append(curnode.left)
17. ifcurnode.right:queue.append(curnode.right)
18. out_list.append(in_list)
19. returnout_list

通过上面的Python伪代码，进行书写更高效的C++代码。

1. classSolution{
2. public:
3. vectorint>>levelOrder(TreeNode*root){
4. vectorint>>res;
5. queueque;
6. //判断root
7. if(root!=nullptr)que.push(root);
8. while(!que.empty()){
9. //开始先求队列的长度
10. intsize=que.size();
11. vector<int>vec;
12. //迭代添加节点元素
13. for(inti=0;i<size;i++){
14. TreeNode*node=que.front();
15. que.pop();
16. vec.push_back(node->val);
17. if(node->left)que.push(node->left);
18. if(node->right)que.push(node->right);
19. }
20. res.push_back(vec);
21. }
22. returnres;
23. }
24. };

上述为树的遍历模板。其实本质上也是深度优先遍历与广度优先遍历的算法模板，许多其它操作都是建立在树遍历操作的基础之上，因此掌握树的所有遍历方法，等于解决了一半树的题目。

原文链接：https://mp.weixin.qq.com/s/dqpQSMx9_iZ4s7z_6L-sNg