二叉树的后续遍历（非递归方式）

视频：https://www.bilibili.com/video/BV1Gb4y1W79d/

TreeNode

public class TreeNode {
    public TreeNode(int data) {
        this.data = data;
    }
    public int data;
    public TreeNode left;
    public TreeNode right;
}

Main函数

public class Test {

    TreeNode root = new TreeNode(1);

    public static void main(String[] args) {
        Test test = new Test();
        test.initTree(test.root);
        test.postOrder(test.root);
    }

    private void postOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode lastVisitNode = null;
        while (current != null) {
            stack.push(current);
            current = current.left;
        }

        while (!stack.empty()) {
            TreeNode stackPopNode = stack.pop();
            if (stackPopNode.right != null && stackPopNode.right != lastVisitNode) {
                stack.push(stackPopNode);
                current = stackPopNode.right;
                while (current != null) {
                    stack.push(current);
                    current = current.left;
                }
            } else {
                System.out.println(stackPopNode.data);
                lastVisitNode = stackPopNode;
            }
        }

    }
    private void initTree(TreeNode root) {
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);

        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);

        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);

        TreeNode node12 = new TreeNode(12);

        root.left = node2;
        root.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.left = node6;
        node3.right = node7;

        node4.left = node8;
        node4.right = node9;

        node5.left = node10;
        node5.right = node11;

        node6.left = node12;
    }