生成二叉树的工具，参考：构建二叉树
打印二叉树的工具类，参考：打印二叉树

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

观察可得，后序遍历就是在【出栈】时，访问【出栈节点】。