leetcode之二叉树中的最大路径和

• 当路径到达某个节点时，该路径既可以前往它的左子树也可以前往它的右子树，但如果路径同时经过它的左右子树，那么就不能经过它的父节点。

class Solution {
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return maxSum;
}
// 返回以 root 为根结点的最大路径和
public int dfs(TreeNode root){
if(root == null) return 0;
int left = dfs(root.left);
int right = dfs(root.right);
// 路径同时经过当前节点及其左右子树的情况。
// 此时不能直接 return left + right + root.val; 是因为 左根右 已经是一条完整的路径了，不能再加上父结点了
if(left >= 0 && right >= 0){
maxSum = Math.max(maxSum, left + right + root.val);
}else if(left <0 && right <0){ // 路径只包含当前节点
maxSum = Math.max(maxSum, root.val);
return root.val;
}
// 路径包含当前节点及其左右子树的任一子树
maxSum = Math.max(maxSum, root.val + Math.max(left, right));
return root.val + Math.max(left, right);
}
}