1. 入栈/出栈顺序
1）打印【入栈】/【出栈】操作工具类
public class BinaryTreeStackPrinter {
public static void recursivePrint(TreeNode root) {
recursivePrint(root, new Stack<>());
}
private static void recursivePrint(TreeNode root, Stack<Integer> stack) {
if (root == null) return;
stack.push(root.val);
System.out.println(root.val + " 【入栈】 | " + stack);
recursivePrint(root.left, stack);
recursivePrint(root.right, stack);
stack.pop();
System.out.println("----------" + root.val + "【出栈】 | " + stack);
}
}
2）构造二叉树进行打印
public class BinaryTreeDemo {
public static void main(String[] args) {
TreeNode root = new BinaryTreeBuilder(3).build();
BinaryTreePrinter.print(root);
BinaryTreeStackPrinter.recursivePrint(root);
}
}
控制台输出：
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 5
===| ┌─┴─┐ ┌─┴─┐
level[3] 节点宽度[ 4]===| 3 4 6 7
1 【入栈】 | [1]
2 【入栈】 | [1, 2]
3 【入栈】 | [1, 2, 3]
----------3【出栈】 | [1, 2]
4 【入栈】 | [1, 2, 4]
----------4【出栈】 | [1, 2]
----------2【出栈】 | [1]
5 【入栈】 | [1, 5]
6 【入栈】 | [1, 5, 6]
----------6【出栈】 | [1, 5]
7 【入栈】 | [1, 5, 7]
----------7【出栈】 | [1, 5]
----------5【出栈】 | [1]
----------1【出栈】 | []
三种遍历方式
public class BinaryTreeStackPrinter {
public static void print(TreeNode root) {
print(root, new Stack<>());
}
private static void print(TreeNode root, Stack<Integer> stack) {
if (root == null) return;
stack.push(root.val);
System.out.println(root.val + " 【入栈】 | " + stack);
// System.out.println("【前序遍历】" + root.val);
print(root.left, stack);
// System.out.println("【中序遍历】" + root.val);
print(root.right, stack);
stack.pop();
System.out.println("----------" + root.val + "【出栈】 | " + stack);
// System.out.println("【后序遍历】" + root.val);
}
}
- 前序遍历输出：
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 5
===| ┌─┴─┐ ┌─┴─┐
level[3] 节点宽度[ 4]===| 3 4 6 7
1 【入栈】 | [1]
【前序遍历】1
2 【入栈】 | [1, 2]
【前序遍历】2
3 【入栈】 | [1, 2, 3]
【前序遍历】3
----------3【出栈】 | [1, 2]
4 【入栈】 | [1, 2, 4]
【前序遍历】4
----------4【出栈】 | [1, 2]
----------2【出栈】 | [1]
5 【入栈】 | [1, 5]
【前序遍历】5
6 【入栈】 | [1, 5, 6]
【前序遍历】6
----------6【出栈】 | [1, 5]
7 【入栈】 | [1, 5, 7]
【前序遍历】7
----------7【出栈】 | [1, 5]
----------5【出栈】 | [1]
----------1【出栈】 | []
观察可得，前序遍历就是在【入栈】时，访问【入栈节点】。
- 中序遍历
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 5
===| ┌─┴─┐ ┌─┴─┐
level[3] 节点宽度[ 4]===| 3 4 6 7
1 【入栈】 | [1]
2 【入栈】 | [1, 2]
3 【入栈】 | [1, 2, 3]
【中序遍历】3
----------3【出栈】 | [1, 2]
【中序遍历】2
4 【入栈】 | [1, 2, 4]
【中序遍历】4
----------4【出栈】 | [1, 2]
----------2【出栈】 | [1]
【中序遍历】1
5 【入栈】 | [1, 5]
6 【入栈】 | [1, 5, 6]
【中序遍历】6
----------6【出栈】 | [1, 5]
【中序遍历】5
7 【入栈】 | [1, 5, 7]
【中序遍历】7
----------7【出栈】 | [1, 5]
----------5【出栈】 | [1]
----------1【出栈】 | []
观察可得，中序遍历就是在【遍历右子树】之前，访问【栈顶节点】。
注意：访问过的节点不需要再访问。
如果【右子树节点】被访问过，说明当前【栈顶节点】已经被访问过了
- 后序遍历
maxLevel: 3
level[1] 节点宽度[ 16]===| 1
===| ┌───┴───┐
level[2] 节点宽度[ 8]===| 2 5
===| ┌─┴─┐ ┌─┴─┐
level[3] 节点宽度[ 4]===| 3 4 6 7
1 【入栈】 | [1]
2 【入栈】 | [1, 2]
3 【入栈】 | [1, 2, 3]
----------3【出栈】 | [1, 2]
【后序遍历】3
4 【入栈】 | [1, 2, 4]
----------4【出栈】 | [1, 2]
【后序遍历】4
----------2【出栈】 | [1]
【后序遍历】2
5 【入栈】 | [1, 5]
6 【入栈】 | [1, 5, 6]
----------6【出栈】 | [1, 5]
【后序遍历】6
7 【入栈】 | [1, 5, 7]
----------7【出栈】 | [1, 5]
【后序遍历】7
----------5【出栈】 | [1]
【后序遍历】5
----------1【出栈】 | []
【后序遍历】1
观察可得，后序遍历就是在【出栈】时，访问【出栈节点】。
网友评论