hasPathSum()
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
We'll define a "root-to-leaf path" to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We'll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths:
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1
For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27.
Given a binary tree and a sum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Return false if no such path can be found. (Thanks to Owen Astrachan for suggesting this problem.)
int hasPathSum(struct node* node, int sum);
----------------------------------------------------------------------------------------------------------------------------
Provided solution is:
int hasPathSum(struct node* node, int sum) {
// return true if we run out of tree and sum==0
if (node == NULL) {
return(sum == 0);
}
else {
// otherwise check both subtrees
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}
I have write following code.
bool hasPathSum(TNodeRef root, int data){
if(!root) return (false); // Will come to this when node have only right or left node (mean not leaf)
if(root->left == NULL && root->right == NULL) return data == root->data;
data -=root->data;
return( hasPathSum(root->left, data)||
hasPathSum(root->right, data));
}
Please comment if this too have mistake.
:)
2 comments:
I'm not getting anything wrong in original solution. Yours is same as that one.
I think both the solutions are fine. In earlier one, there is no check for root->left==NULL and root->left==NULL. But it is not required as when hasPathSum() is called with root=NULL, it simply compare if root->data==0. So it works fine. One more thing is that earlier solution is more readable.
Post a Comment