Метод 1: рекурсивный подход

def path_sum(root, target_sum):
    if not root:
        return 0
    count = 0
    if root.val == target_sum:
        count += 1
    count += path_sum(root.left, target_sum - root.val)
    count += path_sum(root.right, target_sum - root.val)
    return count

Метод 2: итеративный подход с использованием стека

def path_sum(root, target_sum):
    if not root:
        return 0
    stack = [(root, root.val)]
    count = 0
    while stack:
        node, curr_sum = stack.pop()
        if curr_sum == target_sum:
            count += 1
        if node.right:
            stack.append((node.right, curr_sum + node.right.val))
        if node.left:
            stack.append((node.left, curr_sum + node.left.val))
    return count

Метод 3. Поиск в глубину (DFS)

def path_sum(root, target_sum):
    def dfs(node, target):
        if not node:
            return 0
        count = 0
        if node.val == target:
            count += 1
        count += dfs(node.left, target - node.val)
        count += dfs(node.right, target - node.val)
        return count

    if not root:
        return 0
    return dfs(root, target_sum)

Обратите внимание, что код предполагает существование двоичной древовидной структуры с узлами, имеющими атрибут значения (например, root.val) и указатели на левый и правый дочерние элементы (например, root. влево, root.right).