Binary Tree Postorder Traversal 二叉樹的後序周遊（疊代非遞歸版本）

下面來講講疊代版本的二叉樹後序周遊。

首先，我們先來造一個二叉樹，先自己模拟一下後序周遊。

為了便于了解，我在之前的中序周遊的樹上進行了擴充。

1.

回歸一下我們之前的中序周遊，4-3-9,碰到空了就可以停了，但後序周遊是必須左，右子樹都通路了，才可以。

是以，我們還要繼續下去，走到6，然後6再走到4。在這裡我稱為一個叫leftRightMost的周遊：

即如果左子樹不為空，優先走左邊分支；當左子樹為空，走一個右邊的試試；總之，以走左邊的為主。

最後，我們到了4，     4的左右子樹都為空，它可以輸出了。 

2. 接着，我們看看棧的top = 6.  我們将6的右子樹看成一棵獨立的樹，繼續按照1中的做法，找到9這個節點，此時9可以輸出了。

3. 此時top = 6, 同2步驟，我們将7的右子樹看成一棵獨立的樹，走10，輸出10.

4.關鍵的步驟來了，此時棧的top = 7, 此時9， 10都輸出了，是以我們可以輸出7 了。

5. 同樣的，top = 6, top的右節點7已經輸出了，是以，我們可以輸出6了。

之後的步驟就是重複leftRightMost周遊，和看棧的top适不适合輸出。

最後總結: 當且僅當一個節點的left, right = 空 或者，這個節點的右節點已經輸出了，它才能被輸出。

代碼：

public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> store = new Stack<>();
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        putLeftRightMost(store, root);
        TreeNode pre = null;
        while (!store.empty()) {
            TreeNode cur = store.peek();
            if (cur.right == null || cur.right == pre) { // only if one node has no children or his right child has been printed
                pre = store.pop();
                list.add(pre.val);
            } else {
                putLeftRightMost(store, cur.right);
            }
        }
        return list;
    }

    private void putLeftRightMost(Stack<TreeNode> store, TreeNode node) {
        store.push(node);
        node = node.left;
        while (node != null) {
            store.push(node);
            while (node.left != null) {
                store.push(node.left);
                node = node.left;
            }
            node = node.right;
        }
    }