CC27 二叉树中的最大路径和

大致思路：由于最大路径和对应的路径有可能不经过根节点，所以我们需要使用一个变量max来记录最大路径和。遍历左右子树，分别得出左右子树的最大路径和，小于0则记录贡献为0。将根节点的值与左右子树最大路径和相加后与max作比较，大于则替代，反之忽略，这样就可以记录任何可能的最大路径和。最后返回这个max即可。

public class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        dfs(root);
        return max;
    }
    int dfs(TreeNode root){
        if(root == null) return 0;
        
        int left = Math.max(dfs(root.left),0);
        int right = Math.max(dfs(root.right),0);
        int sum = root.val+left+right;
        
        max = Math.max(sum,max);
        return root.val+Math.max(left,right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17