LeetCode 二叉樹最大路徑和 - 遞歸後序遍歷

問題描述

給定二叉樹，找出最大路徑和。路徑可從任意節點開始到任意節點結束，至少包含一個節點。路徑不需經過根節點。

遞歸分析

對每個節點，考慮以該節點為「最高點」的路徑（即路徑穿過該節點，向左和向右各延伸一條鏈）。最大路徑和可能出現在：

1. 左子樹內部
2. 右子樹內部
3. 穿過當前節點：node.val + max(0, leftMax) + max(0, rightMax)

遞歸函數返回：以當前節點為端點的最大鏈和（供父節點使用），即 node.val + max(0, leftMax, rightMax)。

代碼實現（C++）

class Solution {
    int maxSum = INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        maxPath(root);
        return maxSum;
    }
    int maxPath(TreeNode* node) {
        if (!node) return 0;
        int left = max(0, maxPath(node->left));
        int right = max(0, maxPath(node->right));
        maxSum = max(maxSum, node->val + left + right);
        return node->val + max(left, right);
    }
};

關鍵點

• 返回值只能取左或右一條鏈，不能分叉（因為父節點只能延伸一條路徑）。
• 全局變量 maxSum 記錄穿過任意節點的最大路徑和。
• 處理負值：max(0, ...) 表示若子鏈和為負，則不選擇該子鏈（視為空）。
• 初始 maxSum = INT_MIN 確保全負樹也能正確取最大值（單節點）。

複雜度

時間 O(n)，空間 O(h)（遞歸棧深度，h 為樹高）。