Tree traversal: Postorder traversal non-recursion

有兩種方法，都用到 stack

先來看假設一棵樹是 [1, 2, 3, 4, 5, 6, 7]

他的 postorder 是 { 4 ,5 ,2, 6, 7, 3, 1}

如果把上面那個序列從右往回看就是 {1, 3, 7, 6, 2, 5, 4 } -> 是一個 root, right, left 的tree traversal

所以只要把 preorder的方法拿來改一下並且用兩個 stack 來儲存順序在反向印出即可！！

public void postorderTraversal(TreeNode root) {
    if (root == null)
        return;
    }

    Stack<TreeNode> S = new Stack<TreeNode>();
    Stack<TreeNode> res = new Stack<TreeNode>();

    S.push(root);
    while (!S.isEmpty) {

        TreeNode node = S.pop();
        res.push(node);

        //we want right pop first, so push left first
        //don't have to use while to push all left, just this round! think of a sub-case!
        if (node.left != null) {
            S.push(node.left);
        }
        if (node.right != null) {
            S.push(node.right);
        }
    }
    while (!res.isEmpty()) {
        System.out.println(res.pop().val);
    }
}