144. Binary Tree Preorder Traversal

──────────────────────────────────────────────────────────────────────

前序遍歷：先處理自己，再走左子樹，最後走右子樹。

思路

三種深度優先遍歷（前序 / 中序 / 後序）的差別只有一件事：「處理自己」那一行放在哪裡。遞迴版寫熟之後三題等於一題，所以 LeetCode 在這三題都問同一個 follow-up：

Recursive solution is trivial, could you do it iteratively?

iterative 才是這題真正要考的東西。 前序的 iterative 版是三種裡最單純的，因為它的處理順序和「發現順序」一致 —— 走到就處理，不需要記住任何待辦事項。

前序的用途是由上往下傳資訊：父節點先算好某個限制或累積值，再傳給子節點。例如驗證 BST 的上下界、累加根到當前節點的路徑和。這一型的整理見 Tree 遍歷模板。

解題方向

遞迴

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:    
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        res = []
        res.append(root.val)
        res.extend(self.preorderTraversal(root.left))
        res.extend(self.preorderTraversal(root.right))
        return res

這個寫法很好讀 —— 「答案 = 自己 + 左子樹的答案 + 右子樹的答案」直接對應定義。但它有一個效能陷阱：每一層都在複製子樹回傳的整個 list，詳見下面的複雜度。

改成共用一個 res，走到就 append，就是嚴格 $O (n)$ ：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []

        def dfs(node):
            if not node:
                return
            res.append(node.val)      # 前序：處理自己放最前面
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return res

Iterative

一個棧就夠。關鍵是右子節點先進棧、左子節點後進棧 —— 因為棧是後進先出，這樣彈出時才會先拿到左子樹：

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        stack = [root] if root else []

        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)   # 右先進，左才會先出
            if node.left:
                stack.append(node.left)

        return res

前序之所以最好寫，是因為節點被彈出的時機就是該處理它的時機。中序和後序都要「先看過子樹才能處理自己」，所以必須把節點暫存在棧裡等回來 —— 那才是麻煩的地方，見 94. 中序和 145. 後序。

補充

四種遍歷一起看：144. 前序、94. 中序、145. 後序、102. 層序。差別與各自的用途整理在 Tree 遍歷模板。

前序的實戰例子：257. Binary Tree Paths（把路徑往下傳）、105. Construct Binary Tree from Preorder and Inorder Traversal（前序的第一個元素永遠是根）。

複雜度

遞迴（extend 版）

時間 $O (n \log n)$ ~ $O (n^{2})$ — 每一層都複製子樹的 list；平衡樹是 $O (n \log n)$ ，斜樹退化成 $O (n^{2})$
空間 $O (n)$ — 遞迴堆疊在斜樹是 $O (n)$ ，加上中途產生的暫時 list

遞迴（共用 res 版）

時間 $O (n)$ — 每個節點只 append 一次
空間 $O (h)$ — 只有遞迴堆疊，h 是樹高（平衡樹 $O (\log n)$ 、斜樹 $O (n)$ ）

Iterative

時間 $O (n)$ — 每個節點進棧、出棧各一次
空間 $O (h)$ — 棧裡最多同時放一條路徑上的節點

其中 $n$ 是節點數、h 是樹高，都不含輸出的 res。

斜樹為什麼會退化：res = 左 + [自己] + 右 每一層都在建一個新的 list，把子樹的結果整份複製過去。左斜鏈的第 i 層要複製 i 個元素，加總起來就是 $1 + 2 + \dots + n = O (n^{2})$ 。

寫 extend 版沒問題，但要講得出這件事。