Problem
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.
Note: A leaf is a node with no children.
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->2
which sum is 22.
Solution: Recursion
Time complexity: O(n)
Space complexity: O(n)
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua // Running time: 4 ms class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (!root) return false; if (!root->left && !root->right) return root->val==sum; int new_sum = sum - root->val; return hasPathSum(root->left, new_sum) || hasPathSum(root->right, new_sum); } }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment