Binary Tree Maximum Path Sum (Tree + DP)

LC124 題意

• 找出二元樹中 任意兩節點之間的最大路徑和。
• 徑必須連續，且至少包含一個節點。
• Ex.
  Input: [1,2,3] → Output: 6
  Input: [-10,9,20,null,null,15,7] → Output: 42

thoughts

• 對每個節點，考慮「經過該節點的最大路徑」：
  • 左路徑最大和
  • 右路徑最大和
• 可能的最大值 = left + right + node.val
• 回傳值：給父節點的最大單向路徑 = max(left, right) + node.val

Kotlin

class Solution {
    private var maxSum = Int.MIN_VALUE

    fun maxPathSum(root: TreeNode?): Int {
        fun dfs(node: TreeNode?): Int {
            if (node == null) return 0
            val left = maxOf(dfs(node.left), 0)
            val right = maxOf(dfs(node.right), 0)
            maxSum = maxOf(maxSum, node.`val` + left + right)
            return node.`val` + maxOf(left, right)
        }
        dfs(root)
        return maxSum
    }
}

Follow-up

• 若節點可為負數，如何避免取到錯誤的路徑？
  • → 用 max(0, dfs(child)) 避免負貢獻。
• 若要求「節點個數最多的最大路徑」？
  • → 同時計算長度與和。
• 若是有向圖而非樹？
  • → 改用 Topological DP。