EasyTrees
Path Sum
Check if root-leaf path equals target
Solution Approach
Use DFS to explore all root-to-leaf paths. Subtract node value from target and check if any path sums to zero.
Implementation
def hasPathSum(root, targetSum):
if not root:
return False
if not root.left and not root.right:
return targetSum == root.val
return (hasPathSum(root.left, targetSum - root.val) or
hasPathSum(root.right, targetSum - root.val))Complexity Analysis
Time Complexity
O(n)Space Complexity
O(h)Complexity
Time:O(n)
Space:O(h)
Asked at
GoogleMicrosoft