【刷题】二叉树非递归遍历
原题链接：
整体思路
三道题的解决思路可统一，模板也极其相似，比九章提供的更漂亮。
- 将二叉树分为“左”（包括一路向左，经过的所有实际左+根）、“右”（包括实际的右）两种节点
- 使用同样的顺序将“左”节点入栈
- 在合适的时机转向（转向后，“右”节点即成为“左”节点）、访问节点、或出栈
比如{1,2,3}，当cur位于节点1时，1、2属于“左”节点，3属于“右”节点。DFS的非递归实现本质上是在协调入栈、出栈和访问，三种操作的顺序。上述统一使得我们不再需要关注入栈顺序，仅需要关注出栈和访问（第3点），随着更详细的分析，你将更加体会到这种简化带来的好处。
将对节点的访问定义为results.add(node.val);，分析如下：
先序&&中序：
先序和中序的情况是极其相似的。
- 先序的实际顺序：根左右
- 中序的实际顺序：左根右
使用上述思路，先序和中序的遍历顺序可统一为：“左”“右”。
给我们的直观感觉是代码也会比较相似。实际情况正是如此，先序与中序的区别只在于对“左”节点的访问上。
先序的实现
不需要入栈，每次遍历到“左”节点，立即输出即可。
需要注意的是，遍历到最左下的节点时，实际上输出的已经不再是实际的根节点，而是实际的左节点。这符合先序的定义。
while (cur != null) {
results.add(cur.val);
stack.push(cur);
cur = cur.left;
}
而后，因为我们已经访问过所有“左”节点，现在只需要将这些没用的节点出栈，然后转向到“右”节点。于是“右”节点也变成了“左”节点，后续处理同上。
if (!stack.empty()) {
cur = stack.pop();
// 转向
cur = cur.right;
}
完整代码如下：
private List<Integer> dfsPreOrder(TreeNode root) {
ArrayList<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
results.add(cur.val);
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
// 转向
cur = cur.right;
}
return results;
}
中序的实现
基于对先序的分析，先序与中序的区别只在于对“左”节点的处理上，我们调整一行代码即可完成中序遍历。
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
results.add(cur.val); // 仅调整该行代码
// 转向
cur = cur.right;
注意，我们在出栈之后才访问这个节点。因为先序先访问实际根，后访问实际左，而中序恰好相反。相同的是，访问完根+左子树（先序）或左子树+根（中序）后，都需要转向到“右”节点，使“右”节点称为新的“左”节点。
完整代码如下：
private List<Integer> dfsInOrder(TreeNode root) {
List<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
results.add(cur.val);
cur = cur.right;
}
return results;
}
后序
后序的情况略有不同，但仍然十分简洁。
- 后序的实际顺序：左右根
入栈顺序不变，我们只需要考虑第3点的变化（合适时机转向）。出栈的对象一定都是“左”节点（“右”节点会在转向后称为“左”节点，然后入栈），也就是实际的左或根；实际的左可以当做左右子树都为null的根，所以我们只需要分析实际的根。
对于实际的根，需要保证先后访问了左子树、右子树之后，才能访问根。实际的右节点、左节点、根节点都会成为“左”节点入栈，所以我们只需要在出栈之前，将该节点视作实际的根节点，并检查其右子树是否已被访问即可。如果不存在右子树，或右子树已被访问了，那么可以访问根节点，出栈，并不需要转向；如果还没有访问，就转向，使其“右”节点成为“左”节点，等着它先被访问之后，再来访问根节点。
所以，我们需要增加一个标志，记录右子树的访问情况。由于访问根节点前，一定先紧挨着访问了其右子树，所以我们只需要一个标志位。
完整代码如下：
private List<Integer> dfsPostOrder(TreeNode root) {
List<Integer> results = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode last = null;
while(cur != null || !stack.empty()){
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
if (cur.right == null || cur.right == last) {
results.add(cur.val);
stack.pop();
// 记录上一个访问的节点
// 用于判断“访问根节点之前，右子树是否已访问过”
last = cur;
// 表示不需要转向，继续弹栈
cur = null;
} else {
cur = cur.right;
}
}
return results;
}
总结
思路简洁万岁！模板大法万岁！
消灭人类暴政，世界属于三体！
本文链接：【刷题】二叉树非递归遍历 作者：猴子007 出处：monkeysayhi.github.io 本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布，欢迎转载，演绎或用于商业目的，但是必须保留本文的署名及链接。