題目說明

**104. Maximum Depth of Binary Tree
給定一個二元樹，請回傳它的最大深度。
二元樹的深度定義為從根節點到最遠葉子節點的最長路徑上的節點數量。

範例

Input: [3,9,20,null,null,15,7]

3

/
9 20
/
15 7

Output: 3

程式碼

Python 解法
解法 1：遞迴 DFS

class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))

解法 2：BFS（Queue）

from collections import deque
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
depth += 1
return depth

Java 解法

解法 1：遞迴 DFS

public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}

解法 2：BFS（Queue）

import java.util.*;

public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int depth = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        depth++;
    }
    return depth;
}

}

⏱️ 複雜度分析

• 時間複雜度：O(n)，每個節點都會被訪問一次。

• 空間複雜度：

  • 遞迴 DFS：O(h)，h 為樹的高度（最壞 O(n)，最佳 O(log n)）。
  • BFS：O(w)，w 為樹的最大寬度（最壞可能接近 O(n)）。