binarytree这时，我们在二叉树中：初入递归深似海，从此offer递归方式路人之间，实现二叉树的前中后序遍历。二叉树中：听说递归可以，栈也可以！栈用于实现二叉树前后顺序的迭代遍历（非递归）。后来发现迭代方式实现的in-order和in-order其实在风格上不是那么统一，除了pre-order和post-order是有关联的。遍历。实践过的同学也会发现，使用迭代的方式实现中序遍历，很难写出统一的代码，不像递归的方式，实现其中一种遍历方式，另外两种只需要稍微改动一下节点顺序就是这样。其实对于三种遍历方式，使用迭代的方式完全可以写出风格统一的代码！重头戏来了，接下来介绍一下统一的写法。我们以中序遍历为例。二叉树中：听说递归可以，栈也可以！提到如果使用栈，访问节点（遍历节点）和处理节点（将元素放入结果集中）不能同时解决。)不一致。然后我们把访问过的节点入栈，待处理的节点入栈但是标记。如何标记呢，就是把要处理的结点入栈后，马上放一个空指针作为标记。这种方法也可以称为记号法。迭代法中序遍历中序遍历代码如下：（详细注释）classSolution{public:vectorinorderTraversal(TreeNode*root){vectorresult;stackst;if(root!=NULL)st.push(root);while(!st.empty()){TreeNode*node=st.top();if(node!=NULL){st.pop();//弹出节点避免重复操作，然后将右中左节点入栈if(node->right)st.push(node->right);//加入右节点（空节点不入栈）st.push(node);//添加中间节点st.push(NULL);//访问过中间节点，但还没有处理，添加一个空节点作为标记。if(node->left)st.push(node->left);//添加左节点（空节点不入栈）}else{//只有遇到空节点时，才下一个节点放入结果集st.pop();//弹出空节点node=st.top();//重新取出栈中的元素st.pop();result.push_back(node->val);//添加到结果集}}returnresult;}};看代码有点抽象，我们来看动画（中序遍历）：在中序遍历迭代（统一写法）动画中，结果数组是最终结果集。可以看出，我们直接把访问过的节点加入栈中，但是如果是处理过的节点，后面会放一个空节点，这样只有弹出空节点的时候，才把下一个节点放入结果集中。至此，我们再来看一下前序遍历代码。迭代法前序遍历迭代法前序遍历代码如下：（注意，我们此时相比中序遍历只改变了两行代码的顺序）classSolution{public:vectorpreorderTraversal(TreeNode*root){vectorresult;stackst;if(root!=NULL)st.push(root);while(!st.empty()){TreeNode*node=st.top();if(node!=NULL){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();result.push_back(node->val);}}返回结果；}}；迭代后序遍历下面的遍历代码如下：（注意我们此时相比中序遍历只改变了两行代码的顺序）classSolution{public:vectorpostorderTraversal(TreeNode*root){vectorresult;stackst;if(root!=NULL)st.push(root);while(!st.empty()){TreeNode*node=st.top();if(node!=NULL){st.pop();st.push(node);//中间st.push(NULL);if(node->right)st.push(node->right);//右边if(node->left)st.push(node->left);//left}else{st.pop();node=st.top();st.pop();result.push_back(node->val);}}returnresult;}};Summary至此，我们已经写好了一个风格统一的迭代方法，所以我们不用着急在序言中写出来，在inorder写不出来的情况下，但是统一风格的迭代方式不好理解，面试直接写出来还是有难度的。因此，根据个人喜好，对于二叉树的前中后序遍历，选择自己容易理解的递归迭代方式。Java其他语言版本：迭代法的前序遍历代码如下：();if(root!=null)st.push(root);while(!st.empty()){TreeNodenode=st.peek();if(node!=null){st.pop();//弹出节点，避免重复操作，然后将右中左节点入栈if(node.right!=null)st.push(node.right);//添加右节点（空节点为不入栈)if(node.left!=null)st.push(node.left);//添加左节点(空节点不入栈)st.push(node);//添加themiddlenodest.push(null);//中间节点访问，但是还没有处理完，加一个空节点作为标记。}else{//只有遇到空节点时，才将下一个节点放入结果集中st.pop();//弹出空节点node=st.peek();//重新取出stack.pop();result.add(node.val);//添加到结果集中}}returnresult;}}顺序遍历的迭代方法代码如下：classSolution{publicListinorderTraversal(TreeNoderoot){Listresult=newLinkedList<>();Stackst=newStack<>();if(root!=null)st.push(root);while(!st.empty()){TreeNodenode=st.peek();if(node!=null){st.pop();//弹出节点避免重复操作，然后将右中左节点入栈if(node.right!=null)st.push(node.right);//添加右节点(空节点不入栈)st.push(node);//添加中间节点st.push(null);//中间节点已经访问过节点，但还没有处理，添加空节点标记。if(node.left!=null)st.push(node.left);//添加左节点（空节点不入栈）}else{//只有遇到空节点时，下一个节点放入其中Resultsetst.pop();//弹出空节点node=st.peek();//重新取出栈中的元素st.pop();result.add(node.val);//添加到结果集}}returnresult;}}迭代后序遍历代码如下：classSolution{publicListpostorderTraversal(TreeNoderoot){Listresult=newLinkedList<>();Stackst=newStack<>();if(root!=null)st.push(root);while(!st.empty()){TreeNodenode=st.peek();if(node!=null){st.pop();//节点弹出，避免重复操作，然后将右、中、左节点入栈st.push(node);//添加中间节点st.push(null);//中间节点已经访问过，但还没有处理，添加空节点标记。if(node.right!=null)st.push(node.right);//添加右节点(空节点不入栈)if(node.left!=null)st.push(node.left);//添加左边节点（空节点不入栈）}else{//只有遇到空节点时，才将下一个节点放入结果集中st.pop();//弹出空节点node=st.peek();//重新取出栈中的元素st.pop();result.add(node.val);//添加到结果集中}}returnresult;}}Python：迭代前序遍历：classSolution:defpreorderTraversal(self,root:TreeNode)->List[int]:result=[]st=[]ifroot:st.append(root)whilest:node=st.pop()ifnode!=None:ifnode.right:#rightst.append(node.right)ifnode.left:#leftst.append(node.left)st.append(node)#中st.append(None)else:node=st.pop()result.append(node.val)returnresult迭代方法中序遍历：classSolution:definorderTraversal(self,root:TreeNode)->List[int]:result=[]st=[]ifroot:st.append(root)whilest:node=st.pop()ifnode!=None:ifnode.right:#添加右节点（空节点不stacked)st.append(node.right)st.append(node)#添加中间节点st.append(None)#中间节点已经访问过，但是如果还没有处理，添加一个空节点作为标记.ifnode.left:#添加左节点（空节点不入栈）st.append(node.left)else:#只有遇到空节点才将下一个节点放入结果集node=st.pop()#取出栈中的元素result.append(node.val)#添加到结果集returnresult迭代方法后序遍历：classSolution:defpostorderTraversal(self,root:TreeNode)->List[int]:result=[]st=[]ifroot:st.append(root)whilest:node=st.pop()ifnode!=None:st.append(node)#中st.append(None)ifnode.right:#rightst.append(node.right)ifnode.left:#leftst.append(node.left)else:node=st.pop()result.append(node.val)returnresult旧文链接：二叉树：的写法前中序迭代法不能统一什么？
