Leetcode124. 二叉树中的最大路径和(HOT100)
链接
代码：
class Solution {
int res = INT_MIN;
public:
int maxPathSum(TreeNode* root) {
dfs(root);//dfs保证了我们遍历所有二叉树的节点
return res;//res记录最大值
}
int dfs(TreeNode* root){
if(!root)return 0;
//递归计算左子树or右子树的最大值时，如果我们发现值为负数，那么我们不能再往下走了，原因是：我们在更新res时，需要累加l r，累加一个负数的值不是最大的。
int l = max(0,dfs(root->left)),r = max(0,dfs(root->right));//int l = dfs(root->left),r = dfs(root->right);error
res = max(res,root->val+l+r);
return max(l+root->val,r+root->val);//每次向上返回的时候都返回单边，给上面留出来一个接口，不能返回^这个形状，因为我们res已经记录过了
}
};题解：
另外，由于我们在向上返回以及更新res时需要用到l r ，且是累加的方式，那么他俩是小于0的情况时，我们应该和0取max。防止把负数累加到res，以及返回给上一层，这样我们就求不到最大值。