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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int ans = INT32_MIN;
    int maxPathSum(TreeNode* root) {
        // write code here
        calculate(root);
        return ans;
    }


    int calculate(TreeNode* root) { // 计算经过当前节点的最大路径和
        if(root==nullptr) {
            return 0;
        }
        int left = 0;
        int right = 0;
        if(root->left) {
            left = calculate(root->left);
        }
        if(root->right) {
            right = calculate(root->right);
        }

        int val = root->val;
        if(left>0) {
            val+=left;
        }
        if(right>0) {
            val+=right;
        }
        ans= max(ans,val);
        return max(root->val,max(root->val+left,root->val+right));  // 因为只是一边的最大值
    }

};