本文转载自微信公众号《代码随想录》，作者程序员卡尔。转载本文请联系CodeCaprice公众号。二叉树的迭代遍历看完这篇文章，你可以使用迭代的方法，然后在leetcode上重新解决以下三个问题：144.二叉树的前序遍历94.二叉树的中序遍历145.为什么可以用迭代对于二叉树的后序遍历，实现二叉树中序遍历的方法（非递归方式）呢？我们在栈和队列中提到：匹配问题就是栈的强弱。递归的实现是：每次递归调用都会把函数的局部变量、参数值和返回地址压入调用栈，递归返回时，从栈顶弹出上一次递归的参数stack，所以这就是为什么递归可以回到上一级的原因。这时候大家应该知道了，我们还可以利用栈来实现二叉树的前后端后序遍历。前序遍历（迭代法）先来看看前序遍历。前序遍历为中左。每次先处理中间结点，然后根结点先入栈，再右孩子入栈，再加入左孩子。为什么要先加右孩子，再加左孩子呢？因为这是出栈时的中、左、右顺序。动画如下：不难写出如下代码：（注意代码中的空节点没有入栈）classSolution{public:vectorpreorderTraversal(TreeNode*root){stackst;vectorresult;if(root==NULL)returnresult;st.push(root);while(!st.empty()){TreeNode*node=st.top();//inst.pop();result.push_back(node->val);if(node->right)st.push(node->right);//right（空节点不入栈）if(node->left)st.push(node->left);//left(空节点不入栈)}returnresult;}};到这里，你会发现用迭代的方式写一个前序遍历，看似不难，确实不难。这个时候是不是要改变前序遍历代码的顺序，才能把中序遍历出来？事实上，它真的行不通！但是呢，当你用迭代的方式写中序遍历的时候，你会发现套路不一样了。目前前序遍历的逻辑还不能直接应用到中序遍历上。中序遍历（迭代法）为了说明清楚，我先说明一下，在刚才的迭代过程中，我们实际上有两个操作：处理：将元素放入结果数组中访问：遍历节点，分析为什么前序刚写的遍历代码不能和中序遍历通用，因为前序遍历的顺序是中左，先访问的元素是中间节点，要处理的元素也是中间节点，所以目前只能写一个比较简洁的代码，因为需要访问的元素和要处理的元素顺序一致，都是中间节点。然后看中序遍历。中序遍历是左中右。首先访问二叉树顶端的节点，然后逐层访问，直到到达树左侧的底部，然后开始对该节点进行处理（即在Putthevalue节点到结果数组），导致处理顺序和访问顺序不一致。那么在使用迭代的方式写中序遍历的时候，就需要借用指针遍历来帮助访问节点，栈就是用来处理节点上的元素的。动画如下：中序遍历，可以写如下代码：while(cur!=NULL||!st.empty()){if(cur!=NULL){//访问节点的指针，访问底层st.push(cur);//把访问过的节点intothestackcur=cur->left;//left}else{cur=st.top();//从栈中弹出的数据就是要处理的数据（放入result数组的数据）st.pop（）;结果。push_back(cur->val);//中间cur=cur->right;//right}}returnresult;}};后序遍历（迭代法）再来看后序遍历，前序遍历是中左，后续遍历如果是左右，那么只需要调整一下前序遍历的代码顺序变成中-右-左的遍历顺序，再对结果数组进行反转，输出结果顺序为左-右，如下图：所以后序遍历只需要前序遍历的代码即可稍作修改，代码如下：root);while(!st.empty()){TreeNode*node=st.top();st.pop();result.push_back(node->val);if(node->left)st.push(node->left);//相对于前序遍历，这样改变了入栈顺序（空节点不入栈）if(node->right)st.push(node->right);//Empty节点不入栈}reverse(result.begin(),result.end());//之后将结果倒过来，就是左右顺序returnsresult;}};Summary这时候我们就用迭代的方式写出了二叉树的前后端后序遍历。可以看到前序和中序完全是两种代码风格。你不想像递归的写法那样去调整代码来实现从前到后的顺序。这是因为在前序遍历中，访问节点（遍历节点）和处理节点（将元素放入结果数组）可以同步处理，而中序遍历则不能同步！上面这句话可能有的同学看不懂，所以建议自己用迭代的方法，先写preorder，再试着写inorder，就可以理解了。那么问题又来了，二叉树的前向和后向中序遍历的迭代方式是不是可以用统一的方式来实现（即前序遍历可以改变代码顺序来实现中序和后序遍历）后订单）？当然，这种写法不是很好。通俗易懂，我们将在下一篇文章中重点讲解，敬请期待！其他语言版本Java://Preorder遍历顺序：middle-left-right，stackorder：middle-right-leftclassSolution{publicListpreorderTraversal(TreeNoderoot){Listresult=newArrayList<>();if(root==null){returnresult;}Stackstack=newStack<>();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();result.add(node.val);if(node.right!=null){stack.push(node.right);}if(node.left!=null){stack.push(node.left);}}returnresult;}}//Inorder遍历顺序：左-中-右栈顺序：左-右classSolution{publicListinorderTraversal(TreeNoderoot){Listresult=newArrayList<>();if(root==null){returnresult;}Stackstack=newStack<>();TreeNodecur=root;while(cur!=null||!stack.isEmpty()){if(cur!=null){stack.push(cur);cur=cur.left;}else{cur=stack.pop();result.add(cur.val);cur=cur.right;}}returnresult;}}//后序遍历顺序左-右-中堆叠order:middle-left-rightpoppingorder:middle-right-left,最后翻转结果类解决方案{publicListpostorderTraversal(TreeNoderoot){Listresult=newArrayList<>();if(root==null){returnresult;}Stackstack=newStack<>();stack.push(root);while(!stack.isEmpty()){TreeNodenode=stack.pop();result.add(node.val);if(node.left!=null){stack.push(node.left);}if(node.right!=null){stack.push(node.right);}}Collections.reverse(result);returnresult;}}Python:#Preordertraversal-iteration-LC144_二叉树类的Preorder遍历Solution:defpreorderTraversal(self,root:TreeNode)->List[int]:#如果根节点为空，返回空列表ifnotroot:return[]stack=[root]result=[]whilestack:node=stack.pop()#中间节点第一个流程result.append(node.val)#右孩子先入栈ifnode.right:stack.append(node.right)#左孩子后入栈ifnode.left:stack.append(node.left)returnresult#中序遍历-Iteration-LC94_二叉树类的中序遍历解决方法：definorderTraversal(self,root:TreeNode)->List[int]:ifnotroot:return[]stack=[]#根节点不能提前入栈result=[]cur=rootwhilecurorstack:#先迭代访问左下子树节点ifcur:stack.append(cur)cur=cur.left#到达最左边节点后处理栈顶节点else:cur=stack.pop()result.append(cur.val)#取栈顶元素的右节点cur=cur.rightreturnresult#Postordertraversal-iteration-LC145_二叉树类的Postorder遍历解决方案：defpostorderTraversal(self,root:TreeNode)->List[int]:ifnotroot:return[]stack=[root]result=[]whilestack:node=stack.pop()#中间节点先处理result.append(node.val)#左孩子先入栈ifnode.left:stack。append(node.left)#将右孩子入栈ifnode.right:stack.append(node.right)#翻转最终数组returnresult[::-1]
