Binary Tree Maximum Path Sum

https://leetcode.com/problems/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.

解题思路：

这是二叉树遍历比较难得题目，反正我没做出来。

先看看题意，这个最大路径可能是是从树的任意节点到任意节点。开始和结束节点都无需是叶节点或者根节点，甚至路径也可以不经过根节点。任意，于是便没有眉目。

我们思考这个问题。因为路径可能是经过任何节点的，那么这个问题就一定要以每一个节点为root，然后在以它为root的所有路径中找到一个最大值。再在这些所有的最大值中间取一个最大的，就是问题的结果。这里的路径，是无向的，也就是可以从下至上，再从上至下。

第二步很简单，就是维护一个变量，不断去更新他即可。问题是，前一步如何做？

我们考虑任意节点为root，那么以这个节点为root的路径的最大值，一定是它左子树的最大值 + root.val + 右子树的最大值。注意，这里的最大值是有向的，一定是从上至下（或者从下至上，结果是一样的）。当然，如果左子树或者右子树的最大值<0，就不要加上他们。

所以，要解决第一步。我们定义了一个递归的方法，返回的是，从root节点往下的有向路径的最大值。

递归到每个节点的时候，我们都去取它左子节点往下的最大值，和右子节点往下的最大值，然后再去得出从左到右以root为根的路径的最大值。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        int[] max = new int[]{Integer.MIN_VALUE};
        dfs(root, max);
        return max[0];
    }
    
    public int dfs(TreeNode root, int[] max) {
        if(root == null) {
            return 0;
        }
        int leftMax = dfs(root.left, max);
        int rightMax = dfs(root.right, max);
        int maxFromRoot = root.val;
        if(leftMax > 0) {
            maxFromRoot += leftMax;
        }
        if(rightMax > 0) {
            maxFromRoot += rightMax;
        }
        max[0] = Math.max(max[0], maxFromRoot);
        return Math.max(root.val, root.val + Math.max(leftMax, rightMax));
    }
}

这题要特别注意，递归方法返回的不能是maxFromRoot。要清晰的理解递归方法的定义。这里的dfs方法，并不是直接求解最大路径的方法，而是用来递归求每个节点往下的有向路径的最大值。最大路径的计算过程，是通过max这个变量，在递归过程中间自动维护的。

为什么max要用一个数组？因为Java中方法参数传递都是pass by value，不能by reference。对象的内容除外，比如数组，或者list的内容。这里的除外也不是真的除外，是指可以达到by reference的效果。具体不明白的，可以自己去研究一下Java的对象、栈、堆。

http://blog.csdn.net/linhuanmars/article/details/22969069

http://fisherlei.blogspot.sg/2013/01/leetcode-binary-tree-maximum-path-sum.html

Binary Tree Maximum Path Sum

原文：http://www.cnblogs.com/NickyYe/p/4458286.html