Problem: →
https://leetcode.com/problems/path-sum/
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 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
Solution: →
Approach 1: Iterative (DFS)
Time complexity: O(2^n)
Space complexity: O(n)
var hasPathSum = function(root, targetSum) {
if (!root)
return false;
const stack = [];
stack.push(root);
const sum = [];
sum.push(root.val);
while (stack.length) {
const node = stack.pop();
const currSum = sum.pop();
if (currSum === targetSum && !node.left && !node.right)
return true;
if (node.right) {
stack.push(node.right);
sum.push(node.right.val + currSum);
}
if (node.left) {
stack.push(node.left);
sum.push(node.left.val + currSum);
}
}
return false;
};
Approach 2: Recursive (DFS)
var hasPathSum = function(root, targetSum) {
return helper(root, 0, targetSum);
};
var helper = function(root, sum, targetSum) {
if (!root)
return false;
sum += root.val;
if (sum === targetSum && !root.left && !root.right)
return true;
const ans = helper(root.left, sum, targetSum) || helper(root.right, sum, targetSum);
sum -= root.val;
return ans;
};
Approach 3: Recursive – Optimized
var hasPathSum = function(root, targetSum) {
if (!root)
return false;
targetSum -= root.val;
if (targetSum === 0 && !root.left && !root.right)
return true;
const ans = hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
targetSum += root.val;
return ans;
};
Approach 4: Recursive – Further Optimized (Short)
var hasPathSum = function(root, targetSum) {
if (!root)
return false;
if (!root.left && !root.right)
return root.val === targetSum;
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};
Abdullah Mahi 
Leave a comment