Leetcode: Path Sum
Given a binary tree, check if there’s a path such that a targetSum can be reached. A target sum is the sum of values of all visited nodes along the path.
This again can be solved well via recursion. The “trick” is to adapt the targetSum and check at each level. If the tree is empty or if we reach beyond a leaf node, the targetSum cannot be reached.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
newVal = targetSum - root.val
if root.left is None and root.right is None and newVal == 0:
return True
return self.hasPathSum(root.left, newVal) or self.hasPathSum(root.right, newVal)