124. 二叉树中的最大路径和

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
    int ans = INT_MIN;//记录经过当前结点的最大和

public:
    int maxPathSum(TreeNode* root) 
    {
        dfs(root);
        return ans;
    }

    int dfs(TreeNode* root)
    {
        if(!root) return 0;//如果为空，则没有元素求和，为0

        auto left = dfs(root->left);//左子树的最大路径和
        auto right = dfs(root->right);//右子树的最大路径和
        ans = max(ans,left + root->val + right);

        //return max(max(root->val,max(root->val + left,root->val + right)),0);不走+向左走+向右走
        return max(root->val + max(0,max(left,right)),0);//与0比较大小，如果小于0，不要当前结点
    }
};