- Given a Binary Tree, find the maximum sum path from a leaf to root. For example, in the following tree, there are three leaf to root paths 8->-2->10, -4->-2->10 and 7->10. The sums of these three paths are 16, 4 and 17 respectively. The maximum of them is 17 and the path for maximum is 7->10.
10 / \ -2 7 / \ 8 -4
public class PrintMaxSumLeaftoroot {
Node root,leafNode;
public static int max;
public static void main(String[] args) {
PrintMaxSumLeaftoroot tree = new PrintMaxSumLeaftoroot();
tree.root = new Node(10);
tree.root.left = new Node(-2);
tree.root.right = new Node(7);
tree.root.left.left = new Node(8);
tree.root.left.right = new Node(-4);
System.out.println("Following are the nodes "+
"on maximum sum path");
int sum = tree.maxSumPath();
System.out.println("");
System.out.println("Sum of nodes is : " + sum);
}
private int maxSumPath() {
if(root==null)
return 0;
callFinfRoot(root,0);
callprintleaf(root,leafNode);
return max;
}
private boolean callprintleaf(Node root2, Node leafNode2) {
if(root2==null)
return false;
if(leafNode2==root2||callprintleaf(root2.left, leafNode2)||callprintleaf(root2.right, leafNode2))
{
System.out.println(root2.data+" ");
return true;
}
return false;
}
private void callFinfRoot(Node root3, int curentsum) {
if(root3==null)
return ;
curentsum+=root3.data;
if(root3.left==null && root3.right==null)
{
if(curentsum>max)
max=curentsum;
leafNode=root3;
}
callFinfRoot(root3.left,curentsum);
callFinfRoot(root3.right, curentsum);
// TODO Auto-generated method stub
}
}
No comments:
Post a Comment