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

class Solution {
public:
    int maxSum = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);  
        return maxSum;
    }
    int dfs(TreeNode* root) { // 返回以root开头为节点的最大路径长度
        if(!root) return 0;
        int left = max(dfs(root->left), 0); // 分支是否有选取的必要，至少大于0
        int right = max(dfs(root->right), 0);
        maxSum = max(maxSum, left+right+root->val); // 选取中间节点相连的和
        return max(left, right) + root->val;// 选取最大分支构成root开头最大路径长
    }
};