刷Leetcode，需要了解一定的算法模板，这次先总结一下二叉树递归和非递归遍历算法模板。二叉树的四种遍历方式，前中后加层序遍历。对于二叉树的前中后三层的遍历，每次遍历可以采用递归和循环两种方式实现，并且每次遍历的递归实现比循环实现简单。下面我们做一个总结。看了《代码随想录》哈尔滨工业大学的导则，深受启发，因为下面的代码有一定的出处《代码随想录》。下面的递归伪代码是二叉树遍历的递归算法模板。顺序为左中，即前序遍历。把中、左、右三行代码的顺序换一下，前中后三个递归遍历就可以轻松解决了。defpreorderTraversal(root:TreeNode)->List[int]:res=[]defhelp(root):ifnotroot:returnres.append(root.val)#中帮助(root.left)#lefthelp(root.right)#righthelp(root)returnres也为此提供了C++代码，递归算法模板必须加上终止条件，否则递归深似海，offer从此就是路人甲，源码为随机记录的。voidhelp(TreeNode*root,vector&res){if(root==nullptr){return;}res.push_back(root->val);//中间帮助(root->left,res);//lefthelp(root->right,res);//right}vectorpreorderTraversal(TreeNode*root){vectorres;help(root,res);returnres;}迭代遍历二叉树比较难比recursion大，其实就是用了一个栈数据结构。《代码随想录》非常巧妙地使用了一个空指针作为标记。原理是把处理完的结点入栈，然后放一个空指针作为标记。由于栈是先进后出的，所以前序遍历的顺序是中左。添加到栈中时，需要反向添加。每添加一个元素，就在后面添加一个空指针。在Python中，也可以使用None代替。下面是具体的伪代码。至于中序和后序遍历，只要改变入栈节点的顺序即可。defpreorderTraversal(root:TreeNode)->List[int]:result=[]st=[]#1，判断rootifroot:st.append(root)whilest:node=st.pop()ifnode!=None:#rightleftcenter添加到栈中，然后取出指针记录节点st.append(None)else:#node为空指针，则下一个节点为添加的节点node=st.pop()result.append(node.val)returnresult下面是具体的C++代码，因为在C++中出栈后，是没有返回值的，所以需要格外注意。vectorpreorderTraversal(TreeNode*root){vectorres;stackst;if(root!=nullptr)st.push(root);while(!st.empty()){TreeNode*node=st.top();if(node!=nullptr){st.pop();if(node->right)st.push(node->right);if(node->left)st.push(node->left);st.push(node);st.push(NULL);}else{//需要格外注意st.pop();node=st.top();st.pop();res.push_back(node->val);}}returnres;}层次遍历其实树的遍历有两种，分别是深度优先遍历和广度优先遍历。树的不同深度优先遍历（前序、中序、后序遍历）有递归和非递归的写法。树中的广度优先遍历是层次遍历。在二叉树的层次遍历中，我们需要借助队列这个数据结构来帮助我们完成遍历。Python伪代码中，deflevelOrder(root:TreeNode)->List[List[int]]:#1，判断rootifnotroot:return[]#addroottothequenequene=[root]out_list=[]whilequene:#while第一步求lengthlength=len(queue)in_list=[]for_inrange(length):#C++中需要两行curnode=queue.pop(0)#（默认去掉list的最后一个元素）这里通过上面的Python去除in_list.append(curnode.val)ifcurnode.left:queue.append(curnode.left)ifcurnode.right:queue.append(curnode.right)out_list.append(in_list)returnout_list的队首编写更高效的C++代码的伪代码。classSolution{public:vector>levelOrder(TreeNode*root){vector>res;queueque;//判断rootif(root!=nullptr)que.push(root);while(!que.empty()){//先开始求队列长度intsize=que.size();vectorvec;//迭代添加节点元素for(inti=0;i<大小；i++){TreeNode*node=que.front();que.pop();vec.push_back(node->val);if(node->left)que.push(node->left);if(node->right)que.push(node->right);}res.push_back(vec);}returnres;}};以上是树遍历模板。其实本质上是深度优先遍历和广度优先遍历的算法模板。许多其他操作都是基于树遍历操作。因此，掌握了所有的树遍历方法，就相当于解决了一半的树问题。
