Binary Tree Maximum Path Sum

树中任意两点间最大距离

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example: Given the below binary tree,

   1
  / \
 2   3

Return 6.

• Recursively solve this problem
• Get largest left sum and right sum
• Compare to the stored maximum

思路

首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。第一种是左子树的路径加上当前节点，第二种是右子树的路径加上当前节点，第三种是左右子树的路径加上当前节点（相当于一条横跨当前节点的路径），第四种是只有自己的路径。乍一看似乎以此为条件进行自下而上递归就行了，然而这四种情况只是用来计算以当前节点根的最大路径，如果当前节点上面还有节点，那它的父节点是不能累加第三种情况的。所以我们要计算两个最大值，一个是当前节点下最大路径和，另一个是如果要连接父节点时最大的路径和。我们用前者更新全局最大量，用后者返回递归值就行了。

Java代码

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

public int calculateSum(TreeNode root, int[] max) {
  //每次return以root（当前节点）开头最大的单只path sum。
    if (root == null)
        return 0;

    int left = calculateSum(root.left, max);
    int right = calculateSum(root.right, max);

    int current = Math.max(root.val, Math.max(root.val + left, root.val + right));

    //int arch = left + root.val + right;
    //注意arch那条路是不可能走到parent，因为那条路已经经过root了，除非折回来重复走！但这是不允许的 
    max[0] = Math.max(max[0], Math.max(current, left + root.val + right));

    return current;
}