124. Binary Tree Maximum Path Sum

路径在这里定义为树中两点之间的一条线。

如图中的路径最大值为54。注意返回值和max的不同，返回值只能取root的左右任意一边（因为是一条路径）；而max需要当前的root加上它两边的最大值。

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root) {
        if (root == null) return 0;
        int l = Math.max(dfs(root.left), 0);
        int r = Math.max(dfs(root.right), 0);
        max = Math.max(max, l + r + root.val);
        return root.val + Math.max(l, r);
    }
}