Path Sum

Q: Какова временная сложность задачи «Сумма пути»?

O(n) : каждый узел посещается не более одного раза, и поиск может остановиться на первом подходящем листе. Дополнительная память составляет O(h) для исследуемого пути — в виде кадров вызовов или элементов собственного стека.

ЛегкоОбход деревьев

+10

Дано бинарное дерево, хранящееся в массиве tree в порядке уровней, и число targetSum. Корень находится по индексу 0, потомки узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце массива могут находиться дополнительные элементы -1. Верните true, если значения на каком-либо пути от корня до листа в сумме дают targetSum, и false в противном случае. Лист — это узел, у которого оба места для потомков пусты.

Функция

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: двоичное дерево в порядке обхода по уровням, где -1 обозначает пустое место
targetSuminteger: сумма, которой должен достигать путь от корня до листа
Возвращаетboolean: true, если сумма значений на каком-либо пути от корня до листа равна targetSum, в противном случае false

Ограничения

1 ≤ tree.length ≤ 32767
Каждый tree[i] равен -1 или значению, для которого 0 ≤ tree[i] ≤ 1000.
tree[0] никогда не равен -1, поэтому в дереве есть хотя бы один узел.
После последнего узла в массиве могут находиться дополнительные элементы -1.
Оба потомка пустого места тоже пусты, а глубина не превышает 14.
0 ≤ targetSum ≤ 15000

Примеры

Ввод: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Вывод: true
Пояснение: Путь 3, 9, 2 (индексы 0, 1, 4) в сумме дает 14, а 2 с индексом 4 — лист.

Ввод: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Вывод: false
Пояснение: 3 + 9 = 12, но у 9 есть потомок, поэтому ни один путь там не заканчивается. Суммы трёх путей от корня к листу равны 14, 10 и 16, и ни одна из них не равна 12.

Ввод: tree = [4, -1, -1]targetSum = 4
Вывод: true
Пояснение: Оба дочерних места корня пусты, поэтому сам корень является листом. Путь, содержащий только 4, в сумме дает 4.

Дополнительный вопрос

Можешь посчитать количество путей, сумма значений узлов в которых равна targetSum, если путь может начинаться в любом узле и заканчиваться в любом узле ниже него?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Учитываются только полные пути — от корня до листа. Текущая сумма может достичь targetSum в узле, у которого ещё есть дочерние узлы, но такой путь не учитывается. Поэтому передавайте сумму пути вниз к каждому узлу — в качестве параметра или в стеке — и сравнивайте её с целевой суммой только в листьях.

Рекурсия для оставшейся суммы

Идея

Путь, сумма значений которого равна targetSum, начинается со значения корня, поэтому оставшаяся часть пути, начинающаяся в одном из дочерних узлов корня, должна давать сумму, равную targetSum минус значение корня. Это тот же вопрос, но для дерева меньшего размера. По мере спуска вычитайте значение каждого узла; в листе путь заканчивается, поэтому ответ зависит от того, осталось ли что-нибудь.

В первом примере после корня остаётся 14 - 3 = 11, после 9 остаётся 2, а после листа 2 остаётся 0. Во втором после 9 уже остаётся 0, но у него есть дочерний узел, поэтому поиск продолжается. Каждый узел посещается один раз — время O(n), а стек вызовов содержит по одному фрейму на уровень, максимум 15.

Алгоритм

Напиши walk(i, remaining) и вычти tree[i] из remaining.
Если оба дочерних узла i пусты (индекс выходит за конец или равен -1), верни, равно ли remaining 0.
В противном случае верни true, если вызов walk для существующего левого или правого дочернего узла возвращает true.
Верни walk(0, targetSum).

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Поиск в глубину с явным стеком

Идея

Рекурсия хранит одно число на каждый вызов. Вместо этого храните его самостоятельно в стеке рядом с каждым узлом: сумму пути от корня до этого узла. Начните с (0, tree[0]); каждый дочерний узел получает сумму родителя плюс собственное значение. Извлеките пару. Если узел — лист с суммой targetSum, задача решена; иначе добавьте в стек его реальные дочерние узлы.

Каждый реальный узел добавляется в стек один раз: время O(n), а в стеке хранится примерно один ожидающий соседний узел на уровень: O(h). Тот же цикл работает с глубокой деревом на указателях, где рекурсии может не хватить места в стеке.

Алгоритм

Помести (0, tree[0]) в стек.
Извлеки пару (i, total) и проверь дочерние позиции 2*i+1 и 2*i+2.
Если ни один из потомков не существует и total равен targetSum, верни true.
Помести каждого существующего потомка c как (c, total + tree[c]).
Когда стек опустеет, верни false.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Ловушки и крайние случаи

Сравнение суммы в каждом узле. Во втором примере 3 + 9 = 12 совпадает в узле 9, у которого есть потомок, поэтому ответ — false.
Если считать пустое место потомка концом пути. Тогда 9 во втором примере заканчивает путь через пустое место слева от него.
Забывать о корне. Единственный узел — это лист, поэтому [4] с целевой суммой 4 даёт true, как и [0] с целевой суммой 0.
Считывание элементов за концом массива. У листа ближе к концу индексы потомков могут выходить за последний элемент.
Путать смещение в Lua и R. Сохраняйте индексы узлов с отсчётом от 0 для 2*i+1 и считывайте tree[i + 1].

Частые вопросы3

Какова временная сложность задачи «Сумма пути»?

O(n): каждый узел посещается не более одного раза, и поиск может остановиться на первом подходящем листе. Дополнительная память составляет O(h) для исследуемого пути — в виде кадров вызовов или элементов собственного стека.

Можно ли решить задачу о сумме пути с помощью BFS?

Да. Помещайте пары из узла и суммы его пути в очередь вместо стека и проверяйте каждый лист, когда он извлекается. Время работы по-прежнему составляет O(n), но очередь может содержать целый уровень — около половины узлов полного дерева, тогда как стек содержит примерно по одному узлу на уровень.

Как найти все пути, сумма которых равна целевому значению?

По мере спуска сохраняй список узлов текущего пути, копируй его в ответ в каждом листе, сумма которого совпадает, и удаляй последний узел, когда возвращаешься вверх. Обход остаётся прежним. Копирование путей может потребовать больше затрат, чем сам обход, если совпадает много листьев.

def hasPathSum(tree, targetSum):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Ожидаемый вывод

true