题解 | #二叉树的最大路径和#

代码不是我想的，这里只是做出解释

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxSum = INT_MIN;
    int sumPath(TreeNode*root){
        if(!root) return 0;
        auto l = max(0, sumPath(root->left));
        auto r = max(0, sumPath(root->right));
        maxSum = max(maxSum, l + r + root->val);
        return max(l, r) + root->val;
    }
    int maxPathSum(TreeNode* root) {
        // write code here
        sumPath(root);
        return maxSum;
    }
};

这个算法的想法也很简单：

• 计算左子树的最大路径和
• 计算右子树的最大路径和
• 更新树的最大路径和
• 返回此树的最大路径和

巧妙之处在于使用 0 过滤掉了结果为负数的最大路径和

另外将 maxSum 的更新是每次迭代都会进行了，也就是说在每棵子树上都会进行，这样如果出现子树比较大而根节点为负值的情况时，就不会更新 maxSum

说是最大路径和，不如叫做节点的最大和（至少一个节点）