144. Binary Tree Preorder TraversalPreorder Traversal

題目：
給⼀棵⼆元樹，請「先序遍歷（Preorder Traversal）」它，並將節點的值依照順序放入⼀個 List 中返回。

Ｑ：什麼是先序遍歷？
Ａ：根節點 → 左⼦樹 → 右⼦樹

範例：

• Example 1:
  Input: root = [1,null,2,3]
  Output: [1,2,3]
  Explanation:

• Example 2:
  Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
  Output: [1,2,4,5,6,7,3,8,9]
  Explanation:

-Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]

想法：
by遞迴，用自己呼叫自己

程式碼：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root,result);
        return result;
    }
    //幫助函式：用遞迴走訪
    private void traverse(TreeNode node, List<Integer> res){
        if(node == null)return;

        res.add(node.val);          //先加入自己（根）
        traverse(node.left,res);    //再走左邊
        traverse(node.right,res);   //最後走右邊
    }

實際操作：

stack = [1] // 先放 root
output = []

STEP1
取出 stack 最上層元素：node = 1
output = [1]
stack = [] // 把 1 拿掉
：因為 1 有右子樹 → push(2)
：因為 1 沒有左子樹 → 不動作
stack = [2]

STEP2
取出 stack 最上層元素：node = 2
output = [1, 2]
stack = []
：因為 2 沒有右子樹 → 不動作
：因為 2 有左子樹(3) → push(3)
stack = [3]

STEP3
取出 stack 最上層元素：node = 3
output = [1, 2, 3]
stack = []
：因為 3 沒有左右子樹 → 不動作

STEP4
stack 已空，結束遍歷
輸出： [1, 2, 3]