Ratn
BAN USERfirst find the max sum in tree and then search for path for max sum in the tree.
below c++ function will give you the result.
global variable: vector <int> v, int s=0 and int sum=0;
void maxSum(node * root) {
if( root == NULL)
return;
sum += root->data;
maxSum( root->left);
maxSum( root->right);
if( root->left == NULL && root->right == NULL)
if( s < sum ) s = sum;
sum -= root->data;
}
void hasPathSum( node * root, int sum) {
if( root == NULL) return ;
else {
int subSum = sum - root->data;
v.push_back( root->data);
if( subSum == 0 && root->left == NULL && root->right ==NULL)
for( int i=0; i<v.size(); i++) cout<<v[i]<<"->";
hasPathSum(root->left, subSum);
hasPathSum(root->right, subSum);
v.pop_back();
}
}
@REAMS.AL it's just normal tree traversal. just like we do in preOrder / inOrder Traversal. sum(variable) keep adding the root data as we move to left node until reaches the leaf node. When we reach to left most node, sum(variable) will have the sum of all left node value (included root value) and then move to right to explore other possibility. The moment it reaches to leaf node, if s < sum then update s(variable) and decreament the sum by current root->data.
- Ratn October 18, 2012