題目描述:給定一棵二元樹的根節點 root,回傳該樹的「直徑」長度。直徑定義為樹中任意兩個節點之間的最長路徑所包含的邊數。這條路徑不一定需要經過根節點。
解題思路:關鍵觀察是:經過任一節點的最長路徑長度 = 該節點左子樹深度 + 右子樹深度。因此,使用後序 DFS(Post-order DFS)——先遞迴計算左、右子樹的深度,再更新全域最大直徑。每個節點回傳以自身為根的子樹深度(1 + max(left_depth, right_depth)),同時用 left_depth + right_depth 更新答案。整個演算法只需一次 DFS 遍歷,時間複雜度 O(n)。注意:直徑是邊數,不是節點數,但計算深度時以邊為單位(空節點深度為 0),自然得到正確結果。
時間複雜度:O(n) — 每個節點恰好被訪問一次。
空間複雜度:O(h) — 遞迴呼叫堆疊深度等於樹高 h;最壞情況(退化為鏈狀)為 O(n),平衡樹為 O(log n)。
1. Initialize global variable ans = 0 2. Define dfs(node): a. If node is null, return 0 b. left = dfs(node.left) c. right = dfs(node.right) d. ans = max(ans, left + right) // candidate diameter at this node e. Return 1 + max(left, right) // depth of this subtree 3. Call dfs(root) 4. Return ans
暴力法 O(n²):對每個節點分別計算左子樹深度與右子樹深度,再取最大值。重複計算深度導致 O(n²) 時間,但程式碼較直觀,適合初學者理解問題結構。
迭代後序遍歷 O(n):使用明確的堆疊模擬後序 DFS,避免系統遞迴堆疊溢出(對極深樹有利)。邏輯與遞迴版本相同,但需手動管理堆疊狀態,程式碼較繁瑣。