Binary Tree Maximum Path Sum 94
Question
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
这题严格意义上应该属于D&C。singlePath表示以该点为root的子树从root出发能够取的最大path,maxPath表示以该点为root的子树中任意一点到任意一点能取的最大path。
对于每一个node,以该点为root的子树的最大path有两种可能:第一种为不经过该root的path,第二种为经过该root的path。对于第一种情况,最大path为root左边或者右边的最大path,第二种为左边的singlePath + 右边的singlePath+root值。
singlePath的状态函数:max(max(root.left.singlePath, root.rigth.singlePath)+root.val,0),表示若结果为负数,则可以不包含任何点
maxPathd的状态函数:max(root.left.maxPath, root.right.maxPath, root.left.singlePath + root.right.singlePath + root.val),至少包含一个点。
代码如下:
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
class ResultType{
int singlePath;
int maxPath;
public 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) {
// write your code here
ResultType r = helper(root);
return r.maxPath;
}
public ResultType helper(TreeNode root){
if(root == null){
return new ResultType(0, Integer.MIN_VALUE);
}
ResultType left = helper(root.left);
ResultType right = helper(root.right);
//singlePath不一定至少包含一个node
int s = Math.max(Math.max(left.singlePath, right.singlePath) + root.val, 0);
int m = Math.max(left.maxPath, right.maxPath);
m = Math.max(m, left.singlePath + right.singlePath + root.val);
return new ResultType(s, m);
}
}