共计 5994 个字符，预计需要花费 15 分钟才能阅读完成。
之前常常讲波及递归的算法题，我说过写递归算法的一个技巧就是不要试图跳进递归细节，而是从递归框架上思考，从函数定义去了解递归函数到底该怎么实现。
而且咱们前文 学习数据结构和算法的框架思维 特别强调过，练习递归的框架思维最好形式就是从二叉树相干题目开始刷，前文也有好几篇手把手带你刷二叉树和二叉搜寻树的文章：
- 手把手带你刷二叉树（第一期）
- 手把手带你刷二叉树（第二期）
- 手把手带你刷二叉树（第三期）
- 手把手带你刷二叉搜寻树（第一期）
- 手把手带你刷二叉搜寻树（第二期）
- 手把手带你刷二叉搜寻树（第三期）
之前的文章全部都是使用二叉树的递归框架，帮你透过景象看实质，明确二叉树的各种题目实质都是前中后序遍历衍生进去的。
前文 BFS 算法框架详解 是利用队列迭代地遍历二叉树，不过应用的是层级遍历，没有递归遍历中的前中后序之分。
因为当初面试越来越卷，很多读者在后盾问我如何将前中后序的递归框架改写成迭代模式。
首先我想说，递归改迭代从实用性的角度讲是没什么意义的，明明能够写递归解法，为什么非要改成迭代的形式？
对于二叉树来说，递归解法是最容易了解的，非要让你改成迭代，顶多是考查你对递归和栈的了解水平，架不住大家问，那就总结一下吧。
我以前见过一些迭代实现二叉树前中后序遍历的代码模板，比拟短小，容易记，但通用性较差。
通用性较差的意思是说，模板只是针对「用迭代的形式返回二叉树前 / 中 / 后序的遍历后果」这个问题，函数签名相似这样，返回一个 TreeNode 列表：
List<TreeNode> traverse(TreeNode root);
如果给一些略微简单的二叉树问题，比方 最近公共先人，二叉搜寻子树的最大键值和，想把这些递归解法改成迭代，就无能为力了。
而我想要的是一个万能的模板，能够把所有二叉树递归算法都改成迭代。
换句话说，相似二叉树的递归框架：
void traverse(TreeNode root) {if (root == null) return;
/* 前序遍历代码地位 */
traverse(root.left);
/* 中序遍历代码地位 */
traverse(root.right);
/* 后序遍历代码地位 */
}
迭代框架也应该有前中后序代码的地位：
void traverse(TreeNode root) {while (...) {if (...) {/* 前序遍历代码地位 */}
if (...) {/* 中序遍历代码地位 */}
if (...) {/* 后序遍历代码地位 */}
}
}
我如果想把任何一道二叉树递归解法改成迭代，间接把递归解法中前中后序对应地位的代码复制粘贴到迭代框架里，就能够间接运行，失去正确的后果。
实践上，所有递归算法都能够利用栈改成迭代的模式，因为计算机实质上就是借助栈来迭代地执行递归函数的。
所以本文就来利用「栈」模仿函数递归的过程，总结一套二叉树通用迭代遍历框架。
递归框架改为迭代
加入过我的二叉树专项训练的读者应该晓得，二叉树的递归框架中，前中后序遍历地位就是几个非凡的工夫点：
前序遍历地位的代码，会在刚遍历到以后节点 root，遍历root 的左右子树之前执行；
中序遍历地位的代码，会在在遍历完以后节点 root 的左子树，行将开始遍历 root 的右子树的时候执行；
后序遍历地位的代码，会在遍历完以以后节点 root 为根的整棵子树之后执行。
如果从递归代码上来看，上述论断是很容易了解的：
void traverse(TreeNode root) {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 执行完，返回后果并出栈，此时调用栈为空，整个函数调用链完结。
咱们递归遍历二叉树的函数也是一样的，当函数被调用时，被压入调用栈，当函数完结时，从调用栈中弹出。
那么咱们能够写出上面这段代码模仿递归调用的过程：
// 模拟系统的函数调用栈
Stack<TreeNode> stk = new Stack<>();
void traverse(TreeNode root) {if (root == null) return;
// 函数开始时压入调用栈
stk.push(root);
traverse(root.left);
traverse(root.right);
// 函数完结时来到调用栈
stk.pop();}
如果在前序遍历的地位入栈，后序遍历的地位出栈，stk中的节点变动状况就反映了 traverse 函数的递归过程（绿色节点就是被压入栈中的节点，灰色节点就是弹出栈的节点）：
简略说就是这样一个流程：
1、拿到一个节点，就一路向左遍历（因为 traverse(root.left) 排在后面），把路上的节点都压到栈里。
2、往左走到头之后就开始退栈，看看栈顶节点的右指针，非空的话就反复第 1 步。
写成迭代代码就是这样：
private Stack<TreeNode> stk = new Stack<>();
public List<Integer> traverse(TreeNode root) {pushLeftBranch(root);
while (!stk.isEmpty()) {TreeNode p = stk.pop();
pushLeftBranch(p.right);
}
}
// 左侧树枝一撸到底，都放入栈中
private void pushLeftBranch(TreeNode p) {while (p != null) {stk.push(p);
p = p.left;
}
}
上述代码尽管曾经能够模拟出递归函数的运行过程，不过还没有找到递归代码中的前中后序代码地位，所以须要进一步批改。
迭代代码框架
想在迭代代码中体现前中后序遍历，关键点在哪里？
当我从栈中拿出一个节点 p，我应该想方法搞清楚这个节点p 左右子树的遍历状况。
如果 p 的左右子树都没有被遍历，那么当初对 p 进行操作就属于前序遍历代码。
如果 p 的左子树被遍历过了，而右子树没有被遍历过，那么当初对 p 进行操作就属于中序遍历代码。
如果 p 的左右子树都被遍历过了，那么当初对 p 进行操作就属于后序遍历代码。
上述逻辑写成伪码如下：
private Stack<TreeNode> stk = new Stack<>();
public List<Integer> traverse(TreeNode root) {pushLeftBranch(root);
while (!stk.isEmpty()) {TreeNode p = stk.peek();
if (p 的左子树被遍历完了) {
/*******************/
/** 中序遍历代码地位 **/
/*******************/
// 去遍历 p 的右子树
pushLeftBranch(p.right);
}
if (p 的右子树被遍历完了) {
/*******************/
/** 后序遍历代码地位 **/
/*******************/
// 以 p 为根的树遍历完了，出栈
stk.pop();}
}
}
private void pushLeftBranch(TreeNode p) {while (p != null) {
/*******************/
/** 前序遍历代码地位 **/
/*******************/
stk.push(p);
p = p.left;
}
}
有方才的铺垫，这段代码应该是不难理解的，要害是如何判断 p 的左右子树到底被遍历过没有呢？
其实很简略，咱们只须要保护一个 visited 指针，指向「上一次遍历实现的根节点」，就能够判断 p 的左右子树遍历状况了
上面是迭代遍历二叉树的残缺代码框架：
// 模仿函数调用栈
private Stack<TreeNode> stk = new Stack<>();
// 左侧树枝一撸到底
private void pushLeftBranch(TreeNode p) {while (p != null) {
/*******************/
/** 前序遍历代码地位 **/
/*******************/
stk.push(p);
p = p.left;
}
}
public List<Integer> traverse(TreeNode root) {
// 指向上一次遍历完的子树根节点
TreeNode visited = new TreeNode(-1);
// 开始遍历整棵树
pushLeftBranch(root);
while (!stk.isEmpty()) {TreeNode p = stk.peek();
// p 的左子树被遍历完了，且右子树没有被遍历过
if ((p.left == null || p.left == visited)
&& p.right != visited) {
/*******************/
/** 中序遍历代码地位 **/
/*******************/
// 去遍历 p 的右子树
pushLeftBranch(p.right);
}
// p 的右子树被遍历完了
if (p.right == null || p.right == visited) {
/*******************/
/** 后序遍历代码地位 **/
/*******************/
// 以 p 为根的子树被遍历完了，出栈
// visited 指针指向 p
visited = stk.pop();}
}
}
代码中最有技巧性的是这个 visited 指针，它记录最近一次遍历完的子树根节点（最近一次 pop 出栈的节点），咱们能够依据比照 p 的左右指针和 visited 是否雷同来判断节点 p 的左右子树是否被遍历过，进而拆散出前中后序的代码地位。
PS：visited指针初始化指向一个新 new 进去的二叉树节点，相当于一个非凡值，目标是防止和输出二叉树中的节点反复。
只需把递归算法中的前中后序地位的代码复制粘贴到上述框架的对应地位，就能够把任意递归的二叉树算法改写成迭代模式了。
比方，让你返回二叉树后序遍历的后果，你就能够这样写：
private Stack<TreeNode> stk = new Stack<>();
public List<Integer> postorderTraversal(TreeNode root) {
// 记录后序遍历的后果
List<Integer> postorder = new ArrayList<>();
TreeNode visited = new TreeNode(-1);
pushLeftBranch(root);
while (!stk.isEmpty()) {TreeNode p = stk.peek();
if ((p.left == null || p.left == visited)
&& p.right != visited) {pushLeftBranch(p.right);
}
if (p.right == null || p.right == visited) {
// 后序遍历代码地位
postorder.add(p.val);
visited = stk.pop();}
}
return postorder;
}
private void pushLeftBranch(TreeNode p) {while (p != null) {stk.push(p);
p = p.left;
}
}
当然，任何一个二叉树的算法，如果你想把递归改成迭代，都能够套用这个框架，只有把递归的前中后序地位的代码对应过去就行了。
迭代解法到这里就搞定了，不过我还是想强调，除了 BFS 层级遍历之外，二叉树的题目还是用递归的形式来做，因为递归是最合乎二叉树构造特点的。
说到底，这个迭代解法就是在用栈模仿递归调用，所以对照着递归解法，应该不难理解和记忆。
查看更多优质算法文章 点击这里，手把手带你刷力扣，致力于把算法讲清楚！我的 算法教程 曾经取得 90k star，欢送点赞！
