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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int res = -1000000;
    int maxPathSum(TreeNode* root) {
        // write code here
        if(root==nullptr) {
            return 0;
        }
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root) { // 计算的是经过当前节点的路径和
        if(root==nullptr) {
            return ;
        }
        int max_left=-100000,max_right=-1000000;
        calmax(root->left, max_left, 0);
        calmax(root->right, max_right, 0);
        cout<<max_left<<" "<<max_right<<endl;
        res=max(max_left+max_right+root->val,res);
        res=max(res,max_left+root->val);
        res=max(res,max_right+root->val);
        res=max(root->val,res);
        dfs(root->left);
        dfs(root->right);
    }


    void calmax(TreeNode* root,int& ans, int score) { // 计算当前子树最大的路径和
        if(root==nullptr) {
            return;
        }
        ans=max(ans,score+root->val);
        cout<<"ans: "<<ans<<endl;
        calmax(root->left, ans, score+root->val);
        calmax(root->right, ans, score+root->val);
    }
};