Posted on 2013-04-18 21:31
小明 阅读(4000)
评论(0) 编辑 收藏 所属分类:
数据结构和算法
分析：
初看这个问题很难解，可能的路径会非常多，遍历所有的路径，计算量非常大。
二叉树的问题天生适合使用分治算法和递归实现。
对于二叉树
v
/ \
v1 v2
有六种可能最大值v,v1,v2,v+v1,v+v2,v+v1+v2
但是只有v，v+v1，v+v2这三个值的最大者才能返回给上一级。（为什么？因为要形成通往上一层的path，请仔细体会）
代码如下：
public class Solution {
private int max;
private int travel(TreeNode node){
int v = node.val,v1=0,v2=0;
int result = v;
int mlocal = v;
int i = 0;
if(node.left!=null){
v1 = travel(node.left);
if(v1>0){
result = v+v1;
}
if(mlocal<v1){
mlocal = v1;
}
}
if(node.right!=null){
v2 = travel(node.right);
if(result<v+v2){
result = v+v2;
}
if(mlocal<v2){
mlocal = v2;
}
}
if(mlocal<result){
mlocal = result;
}
if(mlocal < v+v1+v2){
mlocal = v+v1+v2;
}
if(max<mlocal){
max = mlocal;
}
return result;
}
public int maxPathSum(TreeNode root) {
max = Integer.MIN_VALUE;
travel(root);
return max;
}
}