題目描述:計算二元樹的最大深度(根節點到最遠葉節點的最長路徑)。
解題思路:遞迴 DFS:空節點深度為 0;任意節點的深度為 1 + max(depth(left), depth(right))。也可用 BFS 層序遍歷,計算層數。遞迴解最為簡潔。
時間複雜度:O(n) — 每個節點訪問一次。
空間複雜度:O(h),h 為樹高 — 遞迴棧深度(平衡樹 O(log n),偏斜樹 O(n))。
1. If root is null: return 0 2. leftDepth = maxDepth(root.left) 3. rightDepth = maxDepth(root.right) 4. Return 1 + max(leftDepth, rightDepth)
層序遍歷 O(n) 時間,O(w) 空間:BFS 逐層,計數層數 — 邏輯相同,空間複雜度可能更差。
迭代 DFS O(n) 時間,O(h) 空間:用堆疊模擬遞迴 — 邏輯相同但程式碼更繁瑣。