之前经常讲涉及递归的算法问题。我说过写递归算法的技巧之一不是试图跳到递归的细节，而是从递归框架和函数定义来思考。了解如何实现递归函数。而我们在上一篇文章中强调了学习数据结构和算法的框架思维。练习递归框架思维的最佳方法是从二叉树相关主题开始。上一篇还有几篇文章会指导大家刷二叉树和二叉查找树：手把手刷二叉树（一期）指导大家手把手刷二叉树（二期）到手把手教你刷二叉树（第三期）手把手教你刷二叉查找树（第一期）手把手教你刷二叉查找树（第二期）带你刷完二分查找树手拉手（第三期）之前的文章都是用二叉树的递归框架，帮你透过现象看本质，理解二叉树各个题目的本质是前中后从遍历派生的延期订单。上一篇BFS算法框架详解，使用队列迭代遍历二叉树，但是使用的是层次遍历，递归遍历不区分前中后序。现在面试越来越复杂，很多读者在后台问我如何把前中后序的递归框架改写成迭代的形式。首先我想说，把递归改成迭代，从实用的角度来说是没有意义的。明明可以写递归解法，那为什么非要改成迭代法呢？对于二叉树，递归的解法是最容易理解的。如果非要改成iterative，顶多是考一下自己对递归和栈的理解。受不了大家问，就总结一下吧。之前看过一些代码模板，迭代实现二叉树的前中后序遍历。它们相对较短且易于记忆，但通用性较差。通用性差意味着该模板只是针对“迭代返回二叉树的前/中/序列的遍历结果”的问题。函数签名与此类似，返回一个TreeNode列表：Listtraverse(TreeNoderoot);如果给你一些稍微复杂的二叉树问题，比如最近共同祖先，二叉搜索子树的最大键值和，想把这些递归的解法改成迭代法，那是无能为力的。而我要的是一个通用的模板，可以把所有的二叉树递归算法都变成迭代。也就是说，一个类似于二叉树的递归框架：voidtraverse(TreeNoderoot){if(root==null)return;/*前序遍历代码位置*/traverse(root.left);/*中序遍历代码位置*/traverse(root.right);/*后序遍历代码位置*/}迭代框架也要有前中后序代码的位置：voidtraverse(TreeNoderoot){while(...){if(...){/*前序遍历代码位置*/}}if(...){/*中序遍历代码位置*/}if(...){/*后序遍历代码位置*/}}If想将任何二叉树递归解法变为迭代法，直接将递归法的前中后序对应的代码复制粘贴到迭代框架中，直接运行即可得到正确的结果。理论上，所有的递归算法都可以通过使用栈变成迭代的形式，因为计算机本质上就是使用栈来迭代执行递归函数。所以本文用“栈”来模拟函数递归的过程，总结出一个通用的二叉树迭代遍历框架。递归框架改为迭代。参加过我二叉树专题培训的读者应该都知道，在二叉树的递归框架中，前中后序遍历位置是几个特殊的时间点：前序遍历位置的代码会遍历到当前节点root在遍历根的左右子树之前执行；中序遍历位置的代码会在遍历完当前节点root的左子树，即将遍历到root的右子树时执行；后序遍历位置的代码，会在遍历完以当前节点root为根的整个子树后执行。如果你看递归代码，上面的结论很容易理解：voidtraverse(TreeNoderoot){if(root==null)return;/*前序遍历代码位置*/traverse(root.left);/*中间的中序遍历代码位置*/traverse(root.right);/*后序遍历代码位置*/}但是，如果我们要把递归算法改成迭代算法，我们无法从框架上理解算法的逻辑，而是需要深入细节，思考计算机是如何工作的做递归。假设计算机运行函数A，它会将A放入调用栈，如果A再次调用函数B，则将B放在A之上，如果B再次调用C，则将C放在B之上……当C执行完毕，C出栈，返回值传给B，B执行完后出栈，返回值传给A，最后A执行完，返回结果，出栈.此时调用栈为空，整个函数调用链结束。我们递归遍历二叉树的功能是一样的。当函数被调用时，它被压入调用栈，当函数结束时，它被从调用栈中弹出。那么我们可以编写如下代码来模拟递归调用的过程：//模拟系统的函数调用栈Stackstk=newStack<>();voidtraverse(TreeNoderoot){if(root==null)return;//在函数开始时压入调用堆栈stk.push(root);遍历（root.left）；遍历（root.right）；//在函数结束时留下调用栈stk.pop();}ifbefore中序遍历的位置入栈，后序遍历的位置出栈.stk中节点的变化反映了遍历函数的递归过程（绿色节点为入栈节点，灰色节点为出栈节点）：简单来说就是这样一个流程：1.得到一个节点，一路向左遍历（因为traverse(root.left)在前面），把路上的所有节点都压入栈中。2、向左走到尽头后，栈会开始展开，查看栈顶节点的右指针，如果不为空，重复步骤1。迭代代码是这样写的：privateStackstk=newStack<>();publicListtraverse(TreeNoderoot){pushLeftBranch(root);while(!stk.isEmpty()){TreeNodep=stk.pop();pushLeftBranch(p.right);}}//将左分支推到最后，入栈privatevoidpushLeftBranch(TreeNodep){while(p!=null){stk.push(p);p=p.左；}}上面的代码虽然已经可以模拟出递归函数的运行过程，但是还没有找到前中后代码在递归代码中的位置，所以还需要进一步修改。迭代代码框架要在迭代代码中体现前中后序遍历。重点在哪里？当我从栈中取出一个节点p时，我应该想办法把这个节点p的左右子树的遍历算出来。如果p的左右子树都没有遍历过，那么现在对p的操作就属于前序遍历代码。如果p的左子树已经遍历完了，但是右子树还没有遍历完，那么现在对p的操作就属于中序遍历的代码。如果已经遍历了p的左右子树，那么现在对p的操作就属于后序遍历代码。上述逻辑写成伪代码如下：privateStackstk=newStack<>();publicListtraverse(TreeNoderoot){pushLeftBranch(root);while(!stk.isEmpty()){TreeNodep=stk.peek();if(p的左子树已经遍历){/********************//**中序遍历代码位置**//***********************//******************//**后序遍历代码位置**//******************///遍历完以p为根的树后，出栈stk.pop();}}}privatevoidpushLeftBranch(TreeNodep){while(p!=null){/******************//**前序遍历代码位置**//******************/stk.push(p);p=p.左；}}有了刚才的铺垫，这段代码应该不难理解了。关键是如何判断p的左右子树是否遍历过？其实很简单。我们只需要维护一个visited指针，指向“上次遍历的根节点”，就可以判断遍历p的左右子树了。下面是迭代遍历二叉树的完整代码框架：//模拟函数调用栈privateStackstk=newStack<>();//left将侧枝推到末尾privatevoidpushLeftBranch(TreeNodep){while(p!=null){/*********************//**前序遍历代码位置**//********************/stk.push(p);p=p.左；}}publicListtraverse(TreeNoderoot){//指向上次遍历的子树的根节点TreeNodevisited=newTreeNode(-1);//开始遍历整棵树pushLeftBranch(root);while(!stk.isEmpty()){TreeNodep=stk.peek();//p的左子树已经遍历完，右子树还没有遍历if((p.left==null||p.left==visited)&&p.right!=visited){/*****************//**中序遍历代码位置**//*******************///要遍历ppushLeftBranch(p.right)的右子树；}//p的右子树已经被遍历if(p.right==null||p.right==visited)/{******************//**后序遍历代码位置**//******************///以p为根的子树已经遍历出栈//visited指针指向p已访问=stk.pop();代码中最有技巧的是visited指针，它记录了最后一次遍历的子树根节点（上次出栈的节点），我们可以通过比较p的左右指针是否是同visited节点p的左右子树是否遍历过，然后把码位分开PS：visited指针初始化指向一个新的二叉树节点，相当于一个特殊的值，目的是以避免与输入二叉树中的节点重复。只需将递归算法中前中后序位置的代码复制粘贴到上述框架的相应位置，任何递归二叉树算法都可以改写成迭代形式。比如要返回二叉树后序遍历的结果，可以这样写：privateStackstk=newStack<>();publicListpostorderTraversal(TreeNoderoot){//记录后序遍历ResultListpostorder=newArrayList<>();TreeNodevisited=newTreeNode(-1);pushLeftBranch（根）；while(!stk.isEmpty()){TreeNodep=stk.peek();if((p.left==null||p.left==visited)&&p.right!=visited){pushLeftBranch(p.right);}if(p.right==null||p.right==visited){//后序遍历代码位置postOSTRDER.Add(p.val);visited=stk.pop();}}ReturnPostorder;}privatevoidPushleftbrance(TreenodeP){While(p!=Null){stk.push(p);p=p.左；}}当然，任何二叉树算法，如果想把递归改成迭代，都可以套用这个框架，只要递归的前、中、后位置的代码与之对应即可。.迭代求解到这里就完成了，不过还是要强调一下，二叉树的问题除了BFS层级遍历外，还是用递归的方式来做的，因为递归最符合二叉树的特性结构。毕竟这个迭代解法是用栈来模拟递归调用，所以相对于递归解法应该不难理解和记忆。查看更多优质算法文章，点这里，小编带你刷理口，力求把算法讲清楚！我的算法教程已获得90kstar，欢迎点赞！
