HardRating 1807

124. Binary Tree Maximum Path Sum

dynamic-programmingtreedepth-first-searchbinary-tree

解題說明

Binary Tree Maximum Path Sum

題目描述：給定二元樹，找出任意節點到任意節點的路徑中，節點值總和最大的路徑和。

解題思路：後序 DFS：對每個節點，計算「以此節點為根向下的最大單邊路徑增益」（取左右子樹增益的正值部分）。同時，用全域變數記錄最大路徑和，更新為 node.val + leftGain + rightGain（左右都延伸的情況）。遞迴函數回傳向上的最大貢獻（只能選一側）。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個節點後序訪問一次。

空間複雜度：O(h) — 遞迴棧深度（h 為樹高）。

虛擬碼

1. maxSum = -infinity
2. DFS(node):
   a. If null: return 0
   b. leftGain = max(0, DFS(left))
   c. rightGain = max(0, DFS(right))
   d. maxSum = max(maxSum, node.val + leftGain + rightGain)
   e. Return node.val + max(leftGain, rightGain)
3. Return maxSum

其他解法

自底向上 DP O(n) 時間，O(h) 空間：遞迴計算每節點的最大路徑和，在遍歷中更新全域最大值 — 邏輯相同，但此即標準方法。

迭代後序遍歷 O(n) 時間，O(h) 空間：顯式堆疊模擬遞迴 — 複雜但避免系統遞迴。

延伸思考

如何找實現最大和的實際路徑（節點序列）？
若路徑必須經過根節點？
若樹是有向圖而非樹？

Binary Tree Maximum Path Sum — CaffeCode