給定一棵二元樹，求其直徑。直徑定義為任意兩個節點之間最長路徑的邊數。此路徑不一定經過根節點。
Example:
Input: root = [1,2,3,4,5] Output: 3 (路徑為 4 -> 2 -> 1 -> 3 或 5 -> 2 -> 1 -> 3)
Intuition
TIP
對每個節點，經過它的最長路徑 = 左子樹高度 + 右子樹高度；全域追蹤最大值。
- 直徑不一定經過根節點，所以要檢查每個節點
- 在計算高度的同時順便更新直徑，一次 DFS 即可完成
Approaches
1. Brute Force (compute per node) — O(n^2) / O(n)
- Idea: 對每個節點計算其左右子樹高度之和，取最大值。每次計算高度需要遍歷子樹。
- Time:
O(n^2)，最差情況下每個節點都要重新計算高度 - Space:
O(n)
class Solution {
fun diameterOfBinaryTree(root: TreeNode?): Int {
if (root == null) return 0
val throughRoot = height(root.left) + height(root.right)
val leftDiameter = diameterOfBinaryTree(root.left)
val rightDiameter = diameterOfBinaryTree(root.right)
return maxOf(throughRoot, leftDiameter, rightDiameter)
}
private fun height(node: TreeNode?): Int {
if (node == null) return 0
return 1 + maxOf(height(node.left), height(node.right))
}
}⭐ 2. DFS Computing Height & Diameter — O(n) / O(h)
- Idea: 在計算每個節點高度的遞迴過程中，同時更新全域直徑變數
- Time:
O(n) - Space:
O(h)
class Solution {
private var diameter = 0
fun diameterOfBinaryTree(root: TreeNode?): Int {
diameter = 0
height(root)
return diameter
}
private fun height(node: TreeNode?): Int {
if (node == null) return 0
val left = height(node.left)
val right = height(node.right)
diameter = maxOf(diameter, left + right)
return 1 + maxOf(left, right)
}
}🔑 Takeaways
- Pattern: 在遞迴中利用「回傳值」和「全域變數」同時追蹤兩個不同的量
- Key trick: 很多樹的最佳化問題（直徑、最大路徑和）都可以在計算高度時順便求解，避免重複遍歷