"""
Exercise 2: Path Sum (LeetCode 112)

Return True if the tree has a ROOT-TO-LEAF path whose values add up to
target_sum. Top-down: pass the remaining sum to the children; check at leaves.
"""

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def has_path_sum(root, target_sum):
    # TODO
    return False


# --- self-check: do not modify below this line ---
def build(level):
    if not level or level[0] is None:
        return None
    root = TreeNode(level[0]); q = [root]; i = 1
    while q and i < len(level):
        n = q.pop(0)
        if i < len(level) and level[i] is not None:
            n.left = TreeNode(level[i]); q.append(n.left)
        i += 1
        if i < len(level) and level[i] is not None:
            n.right = TreeNode(level[i]); q.append(n.right)
        i += 1
    return root

cases = [([5, 4, 8, 11, None, 13, 4, 7, 2, None, None, None, 1], 22, True), ([1, 2, 3], 5, False), ([], 0, False), ([1, 2], 1, False)]
ok = True
for t, s, want in cases:
    got = has_path_sum(build(t), s)
    print(t, s, "->", got)
    ok = ok and got == want
print("PASS" if ok else "FAIL")