124 Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:

Given the below binary tree,

       1
      / \
     2   3

Return 6.

分析&代码

注意！node的val可能是负数！给这题增加了所有的难度！

维持一个全局最大值，初始化为Integer.MIN_VALUE(因为有负值哦)

写一个Helper函数，返回值是经过该点的左路径或右路径中比较大的那个结果

全局最优解是在1.在左右中选一个比较大的结果，或者干脆不选，加上当前节点的值 2.以该节点为根节点，左右路径和+该点的值 中选一个

返回的结果是，必须经过该节点中某一条path最大值（可以不选任何一条路径）

public int maxPathSum(TreeNode root) {
    int[] max = new int[1];
    max[0] = Integer.MIN_VALUE;
    sumPath(root, max);
    return max[0];
}

private int sumPath(TreeNode root, int[] max) {
    if(root == null) {
        return 0;
    }
    int leftRes = Math.max(sumPath(root.left, max), 0);
    int rightRes = Math.max(sumPath(root.right, max), 0);
    int bigger = Math.max(leftRes, rightRes);
    max[0] = Math.max(Math.max(bigger, leftRes + rightRes) + root.val, max[0]);
    return bigger + root.val;
}