二叉树的迭代遍历-栈
二叉树的递归遍历书写简单,做题时能够帮助快速完成dfs
但是往往有某些面试官或者题目要求,使用迭代法完成树的遍历
作为复习材料,不导出推导过程,只给出核心记忆点
TreeNode
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
反序列化工具 BuildTree.toTree(String)
案例
/*
4
/ \
2 6
/ \
1 3
*/
前序遍历(根左右)
- 栈的入栈出栈方向是相反的
- 根节点遍历到就会记录到(从根节点推导出)
root出栈 -> root.right入栈 -> root.left入栈
/**
* 前序遍历 - 根左右 - 迭代法
* - 核心 入栈 根 右 左
*/
public class PreOrder {
public static void main(String[] args) {
String tree = "4,2,6,1,3,#,#,#,#,#,#";
TreeNode root = BuildTree.toTree(tree);
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
ArrayList<Integer> res = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode curr = stack.pop(); // root
res.add(curr.val);
if (curr.right != null) // right
stack.push(curr.right);
if (curr.left != null) // left
stack.push(curr.left);
}
System.out.println("PreOrder=" + res);
}
}
// PreOrder=[4, 2, 1, 3, 6]
后序遍历(左右根)
前序遍历给出的核心入栈出栈操作是:root出栈 -> root.right入栈 -> root.left入栈
对应前序遍历的实际记录顺序是:root -> left -> right
不难看出,left, right 的入栈顺序与实际记录顺序相反,因此如果:
root出栈 -> root.left入栈 -> root.right入栈
那么得到的记录顺序是:root -> right -> left
将记录取反获得:left -> right -> root 为后序遍历顺序
/**
* 后序遍历 - 左右根 - 迭代法
* - 核心 入栈 根 左 右(才前序遍历推导得出), 结果取反
*/
public class PostOrder {
public static void main(String[] args) {
String tree = "4,2,6,1,3,#,#,#,#,#,#";
TreeNode root = BuildTree.toTree(tree);
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
ArrayList<Integer> res = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
res.add(curr.val);
if (curr.left != null)
stack.push(curr.left);
if (curr.right != null)
stack.push(curr.right);
}
int l = 0, r = res.size() - 1;
while (l < r) {
int ll = res.get(l);
int rr = res.get(r);
res.set(l, rr);
res.set(r, ll);
l++;
r--;
}
System.out.println("PostOrder=" + res);
}
}
// PostOrder=[1, 3, 2, 6, 4]
中序遍历(左根右)
访问顺序和记录顺序不一致,单独讨论
中序遍历总是记录每一个节点的左子树后,记录当前节点,再记录右子树
/**
* 中序遍历 - 左根右 - 迭代法
* - 核心 不断将当前节点的左节点入栈, 直到当前节点为null, 弹出后逐个处理右节点
*/
public class InOrder {
public static void main(String[] args) {
String tree = "4,2,6,1,3,#,#,#,#,#,#";
TreeNode root = BuildTree.toTree(tree);
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
ArrayList<Integer> res = new ArrayList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
p = stack.pop();
res.add(p.val);
p = p.right;
}
}
System.out.println("InOrder" + res);
}
}
// InOrder[1, 2, 3, 4, 6]
标签:right,迭代,res,遍历,二叉树,root,stack,left
From: https://www.cnblogs.com/jentreywang/p/17628874.html