Reference
http://www.geeksforgeeks.org/
My approach
http://www.geeksforgeeks.org/
My approach
The approach to find the leaf node which has maximum sum is correct. But after we get the leaf node; we traverse whole tree again to print the full path.
if (root == target_leaf || printPath(root->left, target_leaf) ||
printPath(root->right, target_leaf) )
{
printf("%d ", root->data);
return true;
}
In worst case; if right-most leaf is max-sum-leaf then we traverse tree twice once to find target node and once to print path.
We can improve this by remembering path to target node while finding node itself.
If we can describe path of a node from root node in terms of "L" and "R" i.e. "L" indicated go to left child of current node and "R" indicate go to right child of current node as.
Then we can have a path from root to leaf as LRLRRRL etc.
Once we get the target node we can just check its path string and traverse to that one node directly.
There should be a variable to save path to target node like we have to store max sum.
While finding the target node; we should send current path along with max sum. And as an whenever we update we update max_sum we should update path variable as well.
Then print path will be just check "L" and "R" and go to appropriate node.
Java implementation :-
class MaximumSumPath {
// A utility function that prints all nodes on the path from root to target_leaf
static boolean printPath (TreeNode root, String path)
{
// base case
if (root == null)
return false;
System.out.println(root.key+" ");
TreeNode currNode= root;
for (int i = 0; i<path.length();i++){
if(path.charAt(i)=='L'){
System.out.println(currNode.left.key+" ");
currNode=currNode.left;
}else{
System.out.println(currNode.right.key+" ");
currNode=currNode.right;
}
}
return false;
}
// This function Sets the target_leaf_ref to refer the leaf node of the maximum
// path sum. Also, returns the max_sum using max_sum_ref
static void getTargetLeaf (TreeNode node, int curr_sum, String curr_path, Temp tempObj )
{
if (node == null)
return;
// Update current sum to hold sum of nodes on path from root to this node
curr_sum = curr_sum + node.key;
// If this is a leaf node and path to this node has maximum sum so far,
// then make this node target_leaf
if (node.left == null && node.right == null)
{
if (curr_sum > tempObj.max_value)
{
tempObj.max_value = curr_sum;
tempObj.path=curr_path;
}
}
// If this is not a leaf node, then recur down to find the target_leaf
getTargetLeaf (node.left, curr_sum,curr_path+'L', tempObj);
getTargetLeaf (node.right, curr_sum,curr_path+'R', tempObj);
}
// Returns the maximum sum and prints the nodes on max sum path
static int maxSumPath (TreeNode node)
{
// base case
if (node == null)
return 0;
Temp tempObj= new Temp();
tempObj.max_value=0;
tempObj.path="";
// find the target leaf and maximum sum
getTargetLeaf (node, 0,"", tempObj);
// print the path from root to the target leaf
printPath (node,tempObj.path);
return tempObj.max_value; // return maximum sum
}
public static void main(String args[])
{
TreeNode root = null;
root = new TreeNode (10);
root.left = new TreeNode (-2);
root.right = new TreeNode (7);
root.left.left = new TreeNode (8);
root.left.right = new TreeNode (-4);
System.out.println ("Following are the nodes on the maximum sum path \n");
int sum = maxSumPath(root);
System.out.println("\nSum of the nodes is %d "+sum);
}
}
class Temp{
int max_value;
String path;
}
//Class for a tree node
class TreeNode {
public TreeNode(int key) { this.key = key; left = null; right = null; }
public int key;
public TreeNode left;
public TreeNode right;
}
Output :-
Following are the nodes on the maximum sum path
10
7
No comments:
Post a Comment