LeetCode Binary Tree Maximum Path Sum 二叉樹最大路徑和

題目描述

給定一棵二叉樹，找出任意兩節點間路徑的最大節點值之和。路徑至少包含一個節點，不一定經過根節點。

核心思路：後序遞歸 + 全局最大值維護

對每個節點 root，遞歸計算其左右子樹提供的**最大單邊路徑和**（即以該子樹根為端點、向下延伸的最大和，若為負則視為 0）。

• leftMax = max(0, dfs(root->left))
• rightMax = max(0, dfs(root->right))

以 root 為**最高點**的路徑和為 root->val + leftMax + rightMax，用於更新全局答案 res。
遞歸返回值為 root->val + max(leftMax, rightMax)（單邊延伸供父節點使用）。

完整代碼 (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 {
    int res = INT_MIN;
    int dfs(TreeNode* root) {
        if (!root) return 0;
        int left  = max(0, dfs(root->left));
        int right = max(0, dfs(root->right));
        res = max(res, root->val + left + right);      // 以 root 為頂點的路徑
        return root->val + max(left, right);           // 單邊向上延伸
    }
public:
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }
};

關鍵點總結

• 路徑可不經過根、可只含單節點、可為負值（故初始 res = INT_MIN）。
• 「單邊最大和」若為負則捨棄（取 0），避免拖累父節點。
• 時間 O(N)，空間 O(H)（遞歸棧深度，最壞 O(N)）。