LeetCode Binary Tree Maximum Path Sum：後序遞歸 O(n) 完整解析與 C++ 實作

題目大意

給定一棵二叉樹，找出最大路徑和。路徑可從任意節點開始，到任意節點結束，但必須沿父子連接（不能跳躍）。路徑至少包含一個節點。

範例：

   1
  / \
 2   3
輸出：6 (路徑 2→1→3)

核心觀察

• 對任意節點，最大路徑要么穿過該節點（左子樹最大單邊 + 節點值 + 右子樹最大單邊），要么在左/右子樹內部
• 遞歸函數回傳：以該節點為端點的最大單邊路徑和（供父節點拼接）
• 全域變數維護：全域最大路徑和

遞歸設計

int maxSum = INT_MIN; // 全域最大值

// 回傳：以 root 為端點的最大單邊路徑和（可為 0 表示不取）
int dfs(TreeNode* root) {
    if (!root) return 0;
    int left = max(0, dfs(root->left));   // 負數捨棄，取 0
    int right = max(0, dfs(root->right));

    // 穿過 root 的路徑和
    int cur = root->val + left + right;
    maxSum = max(maxSum, cur);

    // 回傳單邊最大值供父節點使用
    return root->val + max(left, right);
}

完整 C++ 實作

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        maxSum = root ? root->val : 0;
        dfs(root);
        return maxSum;
    }

private:
    int maxSum;

    int dfs(TreeNode* root) {
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        int val = root->val;
        if (left > 0) val += left;
        if (right > 0) val += right;
        if (maxSum < val) maxSum = val;
        return max(max(left, right), 0) + root->val;
    }
};

關鍵細節

1. 負數處理：單邊路徑若為負，捨棄（取 0），因加上負數只會減小總和
2. 初始值：maxSum 初始化為根節點值或 INT_MIN，應對全負數樹
3. 後序遍歷：先遞歸左右子樹，再處理當前節點
4. 時間 O(n)：每節點訪問一次
5. 空間 O(h)：遞歸棧深度，h 為樹高，最壞 O(n)

測試用例

// 單節點
TreeNode* n1 = new TreeNode(-3);          // -3

// 全負數
     -10
     /  \
   -2   -3                               // -2 (路徑 -2)

// 一般情況
       1
      / \
     2   3                               // 6

// 複雜情況
       -10
       /  \
      9    20
          /  \
         15   7                          // 42 (15→20→7)

變體延伸

• 輸出具體路徑：需額外記錄路徑節點，回傳 pair<int, vector<TreeNode*>>
• 路徑長度限制：DP 狀態增加長度維度
• 非二叉樹：多叉樹取最大兩個子樹單邊和

總結

「後序遞歸 + 全域維護 + 單邊回傳」是樹上路徑問題的通用模板。關鍵在於區分作為路徑中間節點（可雙邊）與作為路徑端點（只能單邊）的不同角色，並正確處理負數捨棄邏輯。