LeetCode 解題思路：104. Maximum Depth of Binary Tree（二元樹的最大深度）

luk 收錄於 Leetcode

2024-12-05 約 700 字預計閱讀 4 分鐘

題目描述

給定一個二元樹，返回其最大深度。

二元樹的最大深度是從根節點到最遠葉子節點的最長路徑上的節點數。

注意：葉子節點是指沒有子節點的節點。

範例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：3
解釋：
    3
   / \
  9  20
    /  \
   15   7
最大深度為 3

範例 2：

輸入：root = [1,null,2]
輸出：2
解釋：
  1
   \
    2
最大深度為 2

範例 3：

輸入：root = []
輸出：0
解釋：空樹的深度為 0

限制條件：

樹中節點數的範圍是 [0, 10^4]
-100 <= Node.val <= 100

核心概念理解

什麼是樹的深度？

樹的深度（或高度）是指從根節點到最遠葉子節點的路徑上的節點數量。

深度計算示例：
     1        深度 = 1（只有根節點）
    
     1        
    / \       深度 = 2（最長路徑：1→2 或 1→3）
   2   3      
   
     1
    / \       深度 = 3（最長路徑：1→2→4）
   2   3
  /
 4

重要區別：深度 vs 高度 vs 層級

深度（Depth）：從根節點到當前節點的距離
高度（Height）：從當前節點到最遠葉子節點的距離
層級（Level）：節點所在的層數（根節點為第 1 層）

本題求的是整棵樹的最大深度，等同於根節點的高度。

解法一：遞迴法（DFS - 深度優先搜尋）

思路

遞迴是解決樹問題最自然的方法。核心思想：

樹的最大深度 = max(左子樹深度, 右子樹深度) + 1
空節點的深度為 0

程式碼

# 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: Optional[TreeNode]) -> int:
        # 基本情況：空節點深度為 0
        if not root:
            return 0
        
        # 遞迴計算左右子樹深度
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        # 返回較大深度 + 1（當前節點）
        return max(left_depth, right_depth) + 1

更簡潔的寫法

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

執行過程詳解

對於樹 [3,9,20,null,null,15,7]：

    3
   / \
  9  20
    /  \
   15   7

執行過程：
maxDepth(3)
├─ maxDepth(9)
│  ├─ maxDepth(null) → 0
│  └─ maxDepth(null) → 0
│  → max(0, 0) + 1 = 1
└─ maxDepth(20)
   ├─ maxDepth(15)
   │  ├─ maxDepth(null) → 0
   │  └─ maxDepth(null) → 0
   │  → max(0, 0) + 1 = 1
   └─ maxDepth(7)
      ├─ maxDepth(null) → 0
      └─ maxDepth(null) → 0
      → max(0, 0) + 1 = 1
   → max(1, 1) + 1 = 2
→ max(1, 2) + 1 = 3

複雜度分析

時間複雜度：O(n)
- 每個節點恰好訪問一次
- n 是樹中的節點總數
空間複雜度：O(h)
- h 是樹的高度
- 最壞情況（偏斜樹）：O(n)
- 最好情況（平衡樹）：O(log n)

解法二：BFS（廣度優先搜尋）- 層級遍歷

思路

使用佇列進行層級遍歷，每遍歷完一層，深度加 1。

程式碼

from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        depth = 0
        
        while queue:
            depth += 1
            # 處理當前層的所有節點
            level_size = len(queue)
            
            for _ in range(level_size):
                node = queue.popleft()
                
                # 將下一層的節點加入佇列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        return depth

執行過程視覺化

初始：queue = [3], depth = 0

第 1 層：
  處理節點 3
  queue = [9, 20], depth = 1

第 2 層：
  處理節點 9, 20
  queue = [15, 7], depth = 2

第 3 層：
  處理節點 15, 7
  queue = [], depth = 3

結果：depth = 3

複雜度分析

時間複雜度：O(n)
- 每個節點恰好進出佇列一次
空間複雜度：O(w)
- w 是樹的最大寬度
- 最壞情況（完全二元樹最後一層）：O(n/2) = O(n)

解法三：DFS 迭代法（使用堆疊）

思路

使用堆疊模擬遞迴過程，同時記錄每個節點的深度。

程式碼

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        stack = [(root, 1)]  # (節點, 當前深度)
        max_depth = 0
        
        while stack:
            node, depth = stack.pop()
            max_depth = max(max_depth, depth)
            
            # 將子節點和對應深度壓入堆疊
            if node.right:
                stack.append((node.right, depth + 1))
            if node.left:
                stack.append((node.left, depth + 1))
        
        return max_depth

為什麼先壓入右節點？

因為堆疊是後進先出（LIFO），先壓入右節點可以讓左節點先處理，符合前序遍歷的順序。

解法四：使用內建函數的 Pythonic 解法

方法 1：使用 map 和解構

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(map(self.maxDepth, (root.left, root.right)))

方法 2：使用條件表達式

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return 0 if not root else 1 + max(
            self.maxDepth(root.left), 
            self.maxDepth(root.right)
        )

解法比較

解法	時間複雜度	空間複雜度	優點	缺點
遞迴 DFS	O(n)	O(h)	簡單直觀	可能堆疊溢出
BFS	O(n)	O(w)	適合層級相關問題	需要額外空間存儲佇列
迭代 DFS	O(n)	O(h)	避免遞迴	程式碼較複雜

延伸題目

1. 二元樹的最小深度

def minDepth(self, root: Optional[TreeNode]) -> int:
    if not root:
        return 0
    
    # 如果只有一個子節點，需要繼續往下
    if not root.left:
        return 1 + self.minDepth(root.right)
    if not root.right:
        return 1 + self.minDepth(root.left)
    
    # 兩個子節點都存在
    return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

2. 平衡二元樹檢查

def isBalanced(self, root: Optional[TreeNode]) -> bool:
    def height(node):
        if not node:
            return 0
        
        left_h = height(node.left)
        right_h = height(node.right)
        
        # -1 表示不平衡
        if left_h == -1 or right_h == -1:
            return -1
        if abs(left_h - right_h) > 1:
            return -1
        
        return max(left_h, right_h) + 1
    
    return height(root) != -1

常見錯誤和注意事項

1. 忘記處理空節點

# ❌ 錯誤：沒有檢查 root 是否為空
def maxDepth(self, root):
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

# ✅ 正確：先檢查空節點
def maxDepth(self, root):
    if not root:
        return 0
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

2. BFS 中錯誤的層級處理

# ❌ 錯誤：沒有記錄當前層的節點數
while queue:
    node = queue.popleft()
    depth += 1  # 這樣會對每個節點都加 1

# ✅ 正確：先記錄當前層的節點數
while queue:
    level_size = len(queue)
    for _ in range(level_size):
        node = queue.popleft()
        # 處理節點
    depth += 1

3. 混淆深度和高度

記住：本題求的是從根節點開始的最大深度（節點數），不是邊數！

面試技巧

先寫遞迴解法：最簡單直觀，面試官容易理解你的思路
分析複雜度：明確說明時間和空間複雜度
討論優化：提到 BFS 適合找最小深度（可以提早結束）
處理邊界：空樹、單節點、偏斜樹等特殊情況
擴展思考：如何修改來解決相關問題（最小深度、直徑等）

總結

二元樹的最大深度是樹結構的基礎題目，掌握好這道題對理解樹的遍歷至關重要：

遞迴法最為簡潔優雅，是首選解法
BFS 適合需要層級信息的變形題
迭代 DFS 可以避免遞迴帶來的堆疊溢出風險

關鍵是理解樹的遞迴性質：大問題可以分解為相同的小問題。無論使用哪種方法，核心都是遍歷所有節點並記錄最大深度。

記住口訣：樹的深度 = 子樹深度的最大值 + 1！