思路

树形dp

过程

代码

class Solution 
{
    int ans = INT_MIN;
public:
    int maxPathSum(TreeNode* root) 
    {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root)
    {
        if(root == nullptr) return 0;

        int left = max(0, dfs(root->left));
        int right = max(0, dfs(root->right));
        ans = max(ans, root->val + left + right);
        return root->val + max(left, right);
    }
};