Path Sum

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

Solution

Let $n$ be the number of nodes in the tree.

DFS

Complexity

time: $O(n)$
space: $O(n)$

def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:

    def dfs(node: TreeNode, csum: int) -> bool:
        if not node:
            return False
        csum += node.val
        if not node.left and not node.right and csum == targetSum:
            return True
        return dfs(node.left, csum) or dfs(node.right, csum)

    return dfs(root, 0)