Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
Example
Given the below binary tree:
1
/ 2 3
return 6.
SOLUTION :
解题思路：
首先这题应该有一个fallow up的过程，第一个先问二叉树从root出发到leaf节点最大路径和是多少，第二问如果可以不以Leaf节点结束怎么办，第三问从任一点到任一点。
从这三个follow up过程我们可以发现，这题主要是分清几个不同路线：
1，路线都在左子树上
2，路线都在右子树上
3，路线是从左子树某一点经过root到右子树某一点
具体实现看代码以及备注：
class ResultType{
int singlePath, maxPath;
ResultType(int singlePath, int maxPath){
this.singlePath = singlePath;
this.maxPath = maxPath;
}
}
public class Solution {
/**
* @param root: The root of binary tree.
* @return: An integer.
*/
public int maxPathSum(TreeNode root) {
if (root == null){
return 0;
}
ResultType result = helper(root);
return result.maxPath;
}
private ResultType helper(TreeNode root){
if (root == null){
return new ResultType(0, Integer.MIN_VALUE);
}
//Divide
ResultType left = helper(root.left);
ResultType right = helper(root.right);
//Conquer
//之所以要跟0比较，是因为有负数存在，如果singlepath最大是负数
//根据题意可以全部舍弃
int singlePath = Math.max(0, (Math.max(left.singlePath, right.singlePath) + root.val));
int maxPath = Math.max(left.maxPath, right.maxPath);
maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);
return new ResultType(singlePath, maxPath);
}
}
[Lintcode] Binary Tree Maximum Path Sum
原文：http://www.cnblogs.com/tritritri/p/4858395.html