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

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

點我前往LeetCode題目

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

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

好，相信知道二元樹的情況下，用遞迴走完都不是問題，但題目希望我們挑戰不用遞迴來走完

我們先列出一些重點再來想想要如何解：

1. Node有先後順序問題，先序就是「印出當下Node的val→走左邊→走右邊」，也就是下面還有Node的話，要把當下的Node先記起來，左邊走完再回來這個Node找右邊的Node
2. 下一個Node如果又有Node往下，就又必須記Node
3. 最後記的Node要優先走，然後依序往回找Node

這樣聽起來……似乎stack會符合我們的需求，我們就利用stack後進先出的概念來記Node

我們實際利用程式碼來講解吧！

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

TreeNode currentNode = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> result = new ArrayList<Integer>();

我們用一個currentNode來幫我們指引明燈指出目前我們正在哪個Node
stack則是幫我們暫時記住上面提到的，下面還有Node的Node
result顧名思義就是放結果

while(!stack.isEmpty() || currentNode!=null)

如果stack中還有Node，代表我們是從某個Node往下走，所以還要往回走。而如果stack沒了，currentNode也是空的，就代表我們走完整個二元樹了

if(currentNode!=null){
    result.add(currentNode.val);
    stack.push(currentNode);
    currentNode = currentNode.left;
} else {
    currentNode = stack.pop();
    currentNode = currentNode.right;
}

好的，currentNode!=null是要幹嘛呢？如果他是null的話，代表說stack內有東西的情況下，讀不到東西，代表說我們應該要回頭找右邊的Node了

我們上一個Node存在stack中，所以我們把currentNode移動到stack出來的Node。因為我們是先序走訪，所以這個Node的val已經加過了，就索性直接往右邊走吧

而如果currentNode不是null呢？就更簡單啦，我們把這個currentNode的val丟進result中，然後把currentNode丟到stack中，直接看看他的左邊有沒有Node（沒有的話，下次就會直接走到else中，把這個Node pop掉啦）

那其實LeetCode上先中後序都有出現，中序的概念和這題差不多，大家可以試試看用這一題的邏輯寫出答案（就幾行換個位子而已，免驚）

那後序呢？是不是差不多？

才怪！不一樣啦！