Posted on 2013-04-18 21:31
小明 閱讀(4015)
評(píng)論(0) 編輯 收藏 所屬分類:
數(shù)據(jù)結(jié)構(gòu)和算法
分析：
初看這個(gè)問題很難解，可能的路徑會(huì)非常多，遍歷所有的路徑，計(jì)算量非常大。
二叉樹的問題天生適合使用分治算法和遞歸實(shí)現(xiàn)。
對(duì)于二叉樹
v
/ \
v1 v2
有六種可能最大值v,v1,v2,v+v1,v+v2,v+v1+v2
但是只有v，v+v1，v+v2這三個(gè)值的最大者才能返回給上一級(jí)。（為什么？因?yàn)橐纬赏ㄍ弦粚拥膒ath，請(qǐng)仔細(xì)體會(huì)）
代碼如下：
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;
}
}