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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxSum = INT32_MIN;
    int maxPathSum(TreeNode* root) {
        // write code here
        maxGain(root);
        return maxSum;
    }
    int maxGain(TreeNode* root) { // 返回以当前节点为根的数的最大路径和
        if(!root)
            return 0;
        int left = max(maxGain(root->left),0); // 只有当左右节点超过0时，将左右节点的数值加入
        int right = max(maxGain(root->right),0);
        int num = root->val + left + right; // num表示一条路径的和
        maxSum = max(maxSum, num); // 如果大于maxSum，就将maxSum更新
        return root->val + max(left, right); // 返回以当前节点为根的数的最大路径和
    }
};