題目：
請實作一個後序走訪二元樹的方法

挑戰：
我們知道走訪二元數通常都是用遞迴，你可以在不使用遞迴的情況下搞定這題嗎？

點我前往LeetCode題目

那在開始前不乏提醒一下此系列的固定提醒：

這是一系列逐漸帶入解題的文章，難度會隨著進度增加，若還沒有讀過前面的文章，建議先從最前面開始來逐漸練習解題喔！

本題接續昨日的題目，建議先看一下上一篇，相關的概念就不重複敘述了

可能大家會想說是不是依照昨天那樣，把val加到result，接著用stack來存之後往左走
但這樣會有個問題，我們舉一個比較極端的例子：

依照昨天的邏輯，我們先把1塞進去stack，接著碰到左邊沒有Node，所以1又拿出來。但這時我們沒有要拿1的值，要走右邊之後把1塞回去stack嗎？不行，這樣沒辦法辨識誰是要走右邊，誰是要拿val

因此我們要改點作法，但這次的做法比較不好理解，我們直接從程式碼解釋：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        if(root==null) return result;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode currentNode = root;
        stack.push(currentNode);
        while(!stack.isEmpty())
        {
            currentNode = stack.pop();
            result.addFirst(currentNode.val);
            if(currentNode.left!=null) stack.push(currentNode.left);
            if(currentNode.right!=null) stack.push(currentNode.right);
        }
        return result;
    }
}

LinkedList<Integer> result = new LinkedList<Integer>();
if(root==null) return result;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode currentNode = root;
stack.push(currentNode);

這些基本的東西就不多解釋了

while(!stack.isEmpty())
{
    currentNode = stack.pop();
    result.addFirst(currentNode.val);
    if(currentNode.left!=null) stack.push(currentNode.left);
    if(currentNode.right!=null) stack.push(currentNode.right);
}

那重點的這一段是什麼意思？

首先，後序的讀取順序應該要像下圖這樣

先左邊，再右邊，最後才是自己

而上面的解法是倒過來加答案，上面用了一個addFirst()的方法，它可以幫我們把數字加到最前面。如果每次我們加東西都加在最前面，第一個加進來的東西就會是result內的最後一個對吧？

好像很難懂，我們舉個例子看看

         A
       /   \
     B       E
    / \     / \
   C   D   F   G

照上面程式碼的步驟走一次吧

1. 首先把root的A塞進stack中
2. 進入while迴圈
3. stack pop，currentNode是A
4. 把A加到result最前方，現在result中有[A]
5. 把B塞進stack，再把E塞進stack，stack中現在有[E,B]
6. stack pop，currentNode現在是E
7. 把E加到result最前方，現在result中有[E,A]
8. 把F塞進stack，再把G塞進stack，stack中現在有[G,F,B]
9. stack pop，currentNode現在是G
10. G下面沒有Node，所以G直接進result最前方，result中現在有[G,E,A]
11. stack pop，currentNode現在是F
12. F下面沒有Node，所以F直接進result最前方，result中現在有[F,G,E,A]
13. stack pop，currentNode現在是B（注意這裡切換到root左邊了）
14. 把B加到result最前方，現在result中有[B,F,G,E,A]
15. 把C塞進stack，再把D塞進stack，stack中現在有[D,C]
16. stack pop，currentNode現在是D
17. D下面沒有Node，所以D直接進result最前方，result中現在有[D,B,F,G,E,A]
18. stack pop，currentNode現在是C
19. C下面沒有Node，所以C直接進result最前方，result中現在有[C,D,B,F,G,E,A]
20. stack空了，輸出答案

我們拿到的root，本身就是後序走訪中的最後一個，我們剛好可以利用這一點，反過來加答案。

每一次我們到的新Node，把它之下的整個結構，想像成是一棵小一點的二元樹，這樣那顆新的Node就變成另一個root了對吧？
那新的Node就都是最後一個讀取的，所以就把它加到最前面，再往下找其他Node。while迴圈內就是在處理這一件事