144. Binary Tree Preorder TraversalPreorder Traversal

解法貳：迭代解

想法：
by迭代解

1. 使⽤ Stack。
2. 起點放進 stack（根節點）。
3. 當 stack 非空：
   拿出最上⾯的節點，加入結果（代表拜訪它）。
   注意：先放右邊，再放左邊，這樣左邊會先
   被處理（stack 是後進先出 LIFO）。

程式碼（迭代解）：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);//拜訪節點

            //注意順序：右邊先 push，這樣左邊會先出來
            if(node.right != null) stack.push(node.right);
             if(node.left != null) stack.push(node.left);
        }
        return result;
    }
}

實際操作：

stack = [1]
result = []

STEP1
stack = [1]
result = []
：因為 1.right = 2 → push(2)
：因為 1.left = null → 不動作
stack = [2]

STEP2
pop = 2
result = [1] → [1, 2]
：因為 2.right = null → 不動作
：因為 2.left = 3 → push(3)
stack = [3]

STEP3
pop = 3
result = [1, 2] → [1, 2, 3]
：因為 3.right = null → 不動作
：因為 3.left = null → 不動作
stack = []

STEP4
stack 已空 → 結束
輸出： [1, 2, 3]

兩者比較：
簡單易懂：遞迴
處理很⼤的樹：選擇迭代，避免 stack overflow 錯誤