112. Path Sum
1. Description
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.
2. Note
- A leaf is a node with no children.
3. Solutions
Recursive
n is the number of nodes in the tree
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
bool hasPathSum(TreeNode *root, int targetSum) {
if (root != nullptr) {
if (root->left == nullptr && root->right == nullptr && root->val == targetSum) {
return true;
} else {
return hasPathSum(root->left, targetSum - root->val) ||
hasPathSum(root->right, targetSum - root->val);
}
} else {
return false;
}
}
};