In this guide, you will get 112. Path Sum LeetCode Solution with the best time and space complexity. The solution to Path Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 –> 2): The sum is 3.
(1 –> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.
Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.
Constraints:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(h)
112. Path Sum LeetCode Solution in C++
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == nullptr)
return false;
if (root->val == sum && root->left == nullptr && root->right == nullptr)
return true;
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}
}; /* code provided by PROGIEZ */
112. Path Sum LeetCode Solution in Java
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
if (root.val == sum && root.left == null && root.right == null)
return true;
return //
hasPathSum(root.left, sum - root.val) || //
hasPathSum(root.right, sum - root.val);
}
} // code provided by PROGIEZ
112. Path Sum LeetCode Solution in Python
class Solution:
def hasPathSum(self, root: TreeNode, summ: int) -> bool:
if not root:
return False
if root.val == summ and not root.left and not root.right:
return True
return (self.hasPathSum(root.left, summ - root.val) or
self.hasPathSum(root.right, summ - root.val)) # code by PROGIEZ
