---
title: "104. Maximum Depth of Binary Tree"
url: "https://laigary.com/interview/coding/104-maximum-depth-of-binary-tree"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Tree", "Depth-First Search", "Postorder Traversal"]
---

# 104. Maximum Depth of Binary Tree

[104\. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

回傳二元樹的最大深度（從根到最遠葉節點的節點數）。

## 思路

這題是**後序型遞迴的最小範例**，樹的中難題有一大半都是它的變形，所以值得把「為什麼這樣寫」講到很清楚。

樹的遞迴只要回答兩個問題：**用哪種遍歷**、**遞迴要回傳什麼給父節點**。

這題的答案是：

> 回傳「**以我為根的這棵子樹有多深**」。

一旦這樣定義，遞迴式就自己浮出來了 —— 我的深度 = 左右子樹裡比較深的那個 + 1（那個 1 是我自己）。而且**必須等左右都算完才能算我自己**，這就是後序。

`base case` 的選擇也是從定義推出來的：空樹的深度是 **0**，不是 1、也不是 `None`。定義清楚了，`max(left, right) + 1` 對葉節點自動成立（兩邊都是 0，得到 1），不需要為葉節點寫特例。

**面試時的講法**：先說「我讓遞迴回傳子樹的深度」，再寫程式碼。多數人卡住是因為沒先把回傳值的語意定義出來就開始寫。

## 解題方向

```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 maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1
```

把 `left` 和 `right` 拆成兩行而不是寫成一行 `return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1`，是刻意的好習慣：一旦題目變成「還要拿子樹的值做別的事」（例如 [543. Diameter](/interview/coding/543-diameter-of-binary-tree) 要把左右相加），你只要在中間插一行，不用改結構。

## 補充

**同一個骨架的變形**，差別只在「拿到左右子樹的值之後做什麼」：

| 題目 | 回傳給父節點 | 答案怎麼取 |
|---|---|---|
| 104 這題 | 子樹深度 | 就是回傳值 |
| [543. Diameter of Binary Tree](/interview/coding/543-diameter-of-binary-tree) | 子樹深度（一樣） | **左 + 右**，用外部變數記最大 |
| [124. Binary Tree Maximum Path Sum](/interview/coding/124-binary-tree-maximum-path-sum) | 單邊最大路徑和 | 左 + 右 + 自己，外部變數記最大 |
| [337. House Robber III](/interview/coding/337-house-robber-iii) | (偷我, 不偷我) 兩個值 | 根節點兩者取 max |

543 和 124 的共同重點是：**回傳給父節點的值，和答案要的值不一樣**。這是後序型題目最容易卡住的地方，而 104 因為兩者剛好相同，所以是最好的入門。

**最小深度不是把 `max` 改成 `min`**：[111. Minimum Depth of Binary Tree](/interview/coding/111-minimum-depth-of-binary-tree) 要求到**葉節點**的最短距離，單邊為空的節點不是葉節點，所以要特別處理，否則會回傳 0。這是很常見的陷阱題。

**N-ary 版本**：[559. Maximum Depth of N-ary Tree](/interview/coding/559-maximum-depth-of-n-ary-tree)，把 `max(left, right)` 換成對 `children` 取 max 就好。

整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

- 時間 $O(n)$ — 每個節點造訪一次
- 空間 $O(h)$ — 遞迴堆疊，`h` 是樹高

其中 `n` 是節點數、`h` 是樹高。平衡樹的 `h` 是 $O(\log n)$，退化成一條鏈時是 $O(n)$ —— 樹的遞迴題空間永遠是這個答案，被問到就這樣講。