Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
- Given the below binary tree and sum = 22,
5
/
4 8
/ /
11 13 4
/
7 2 1
- return true, as there exist a root-to-leaf path
5->4->11->2which sum is 22.
C Solution 1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool preorder(struct TreeNode *root, int cur, int sum) {
if (!root->left && !root->right) return root->val + cur == sum;
if (root->left && preorder(root->left, root->val + cur, sum)) return true;
if (root->right && preorder(root->right, root->val + cur, sum)) return true;
return false;
}
bool hasPathSum(struct TreeNode* root, int sum) {
if (!root) return false;
return preorder(root, 0, sum);
}
C Solution 2:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool hasPathSum(struct TreeNode* root, int sum) {
if (!root) return false;
if (!root->left && !root->right) return root->val == sum;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
Summary:
- Always check whether root is null first?
- Solution 2 is much better.
LeetCode: 112. Path Sum
近期评论