The key is from root to leave, add up the node value and pass the sum to the lower levels.
public static int maxSumFromRootHelper(Node root, int sum){
if(root == null)
return sum;
else{
return Math.max(maxSumFromRootHelper(root.left, root.data + sum),
maxSumFromRootHelper(root.right, root.data + sum));
}
}
//store the max sum result
static int max_sum = Integer.MIN_VAL;
//store the leaf
static Node maxNode = null;
public static void findLeaveWithMaxSumFromRoot(Node root, int sum){
if(root == null)
return;
sum = sum + root.data;
if(root.left == null && root.right ==null){
if(sum > max_sum){
max_sum = sum;
maxNode = root;
}
}
else{
findLeaveWithMaxSumFromRoot(root.left, sum);
findLeaveWithMaxSumFromRoot(root.right, sum);
}
}
No comments:
Post a Comment