题解 | #二叉树中的最大路径和# 11-3 03 递归左右子树 dfs，

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    /*
        dfs:返回当前子树能向父节点提供的最大路径和。
        有三种情况：
        1，路径停留在当前子树的根节点，贡献root->val
        2，进入左子树，贡献XXX
        3，进入右子树，贡献XXX
        对应前面的三种选择，最大贡献者选择最大
        root->val = max(left, right)
    */
    int ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        // write code here
        if (!root) {
            return 0;
        }
        dfs(root);
        return ans;
    }
    int dfs(TreeNode* root) {
        if (!root) {
            return 0;
        }
        // 计算左右节点
        int leftChild = max(dfs(root->left), 0);
        int rightChild = max(dfs(root->right), 0);
        
        // 更新ans
        ans = max(ans, leftChild + rightChild + root->val);
        // 返回当前节点的总贡献
        return root->val+max(leftChild,rightChild);
    }
};