給定一棵二元樹，找到路徑和最大的路徑。路徑定義為從任意節點出發沿著父子連接到達任意節點的序列，路徑不需要經過根節點，每個節點最多出現一次。
Example:
Input: root = [-10,9,20,null,null,15,7] Output: 42 (路徑為 15 -> 20 -> 7)
Intuition
TIP
對每個節點，計算「經過它的最大路徑和」= 節點值 + 左邊最大貢獻 + 右邊最大貢獻；但回傳給父節點時只能選一邊。
- 關鍵區分：
- 「經過該節點的完整路徑」可以同時包含左右子路徑（用於更新全域最大值）
- 「回傳給父節點的貢獻」只能選左或右其中一邊（因為路徑不能分叉）
- 貢獻值為負時，取 0（不選該子路徑）
Approaches
1. Brute Force (enumerate all paths) — O(n^2) / O(n)
- Idea: 對每個節點作為路徑的最高點，嘗試所有可能的左右延伸組合
- Time:
O(n^2) - Space:
O(n)
class Solution {
fun maxPathSum(root: TreeNode?): Int {
var maxSum = Int.MIN_VALUE
fun maxGain(node: TreeNode?): Int {
if (node == null) return 0
return node.`val` + maxOf(maxGain(node.left), maxGain(node.right), 0)
}
fun traverse(node: TreeNode?) {
if (node == null) return
val left = maxOf(maxGain(node.left), 0)
val right = maxOf(maxGain(node.right), 0)
maxSum = maxOf(maxSum, node.`val` + left + right)
traverse(node.left)
traverse(node.right)
}
traverse(root)
return maxSum
}
}⭐ 2. Single DFS (compute gain & update max) — O(n) / O(h)
- Idea: 遞迴計算每個節點的最大單邊貢獻，同時用「節點值 + 左貢獻 + 右貢獻」更新全域最大路徑和
- Time:
O(n) - Space:
O(h)
class Solution {
private var maxSum = Int.MIN_VALUE
fun maxPathSum(root: TreeNode?): Int {
maxSum = Int.MIN_VALUE
maxGain(root)
return maxSum
}
private fun maxGain(node: TreeNode?): Int {
if (node == null) return 0
val leftGain = maxOf(maxGain(node.left), 0)
val rightGain = maxOf(maxGain(node.right), 0)
// 經過此節點的完整路徑和
maxSum = maxOf(maxSum, node.`val` + leftGain + rightGain)
// 回傳給父節點的最大貢獻（只能選一邊）
return node.`val` + maxOf(leftGain, rightGain)
}
}Why the return value can pick only one side?
路徑是一條線，不能分叉。如果一個節點回傳給父節點的貢獻同時包含左右子路徑，那加上父節點後路徑就會形成「T 字形」分叉，這不符合路徑的定義。
所以：
- 更新全域最大值時可以用
左 + 根 + 右（此路徑以該節點為頂點） - 回傳給父節點時只能用
根 + max(左, 右)（作為父節點路徑的一部分）
🔑 Takeaways
- Pattern: 「回傳值」用於向上傳遞貢獻，「全域變數」用於追蹤最佳完整路徑 — 和 Diameter of Binary Tree 相同模式
- Key trick: 區分「完整路徑」和「單邊貢獻」是解決樹路徑問題的核心思維