Posted on 2013-04-18 21:31
小明 閱讀(4013)
評論(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;
}
}