---
title: "144. Binary Tree Preorder Traversal"
url: "https://laigary.com/interview/coding/144-binary-tree-preorder-traversal"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-28"
tags: ["Preorder Traversal", "Tree"]
---

# 144. Binary Tree Preorder Traversal

[144\. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)

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

## 思路

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

> Recursive solution is trivial, could you do it iteratively?

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

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

## 解題方向

### 遞迴

```python
# 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)$：

```python
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

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

```python
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. 中序](/interview/coding/94-binary-tree-inorder-traversal) 和 [145. 後序](/interview/coding/145-binary-tree-postorder-traversal)。

## 補充

**四種遍歷一起看**：[144. 前序](/interview/coding/144-binary-tree-preorder-traversal)、[94. 中序](/interview/coding/94-binary-tree-inorder-traversal)、[145. 後序](/interview/coding/145-binary-tree-postorder-traversal)、[102. 層序](/interview/coding/102-binary-tree-level-order-traversal)。差別與各自的用途整理在 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

**前序的實戰例子**：[257. Binary Tree Paths](/interview/coding/257-binary-tree-paths)（把路徑往下傳）、[105. Construct Binary Tree from Preorder and Inorder Traversal](/interview/coding/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` 版沒問題，但要講得出這件事。