Giuss
BAN USERpackage SubTreeLargestSumUp;
public class BTNode {
public BTNode left;
public BTNode right;
public int value;
public int sumUp;
public BTNode(BTNode l, BTNode r, int v, int s){
left = l;
right = r;
value = v;
sumUp = s;
}
}
package SubTreeLargestSumUp;
public class BTNode {
public BTNode left;
public BTNode right;
public int value;
public int sumUp;
public BTNode(BTNode l, BTNode r, int v, int s){
left = l;
right = r;
value = v;
sumUp = s;
}
}
package SubTreeLargestSumUp;
public class DFS {
BTNode r = new BTNode(null, null, 0, Integer.MIN_VALUE);
public static void main(String [] args){
BTNode a = new BTNode(null, null, 4, Integer.MIN_VALUE);
BTNode b = new BTNode(null, null, 5, Integer.MIN_VALUE);
BTNode c = new BTNode(null, null, -1, Integer.MIN_VALUE);
BTNode d = new BTNode(null, null, 7, Integer.MIN_VALUE);
BTNode e = new BTNode(c, d, 3, Integer.MIN_VALUE);
BTNode f = new BTNode(a, b, 2, Integer.MIN_VALUE);
BTNode g = new BTNode(e, f, 1, Integer.MIN_VALUE);
DFS dfs = new DFS();
dfs.sumUp(g);
System.out.print(dfs.DFS(g).value);
}
public int sumUp(BTNode n){
if (n.left == null && n.right == null)
return n.sumUp = n.value;
else if (n.left == null)
return n.sumUp = n.value + sumUp(n.right);
else if (n.right == null)
return n.sumUp = n.value + sumUp(n.left);
else return n.sumUp = n.value + + sumUp(n.left) + + sumUp(n.right);
}
public BTNode DFS(BTNode n){
if (n.left != null)
DFS(n.left);
if (n.right != null)
DFS(n.right);
if (n.sumUp > r.sumUp) r = n;
return r;
}
}
- Giuss March 01, 2012