Path Sum

+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.

+14 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

Сначала разберёмся, как перемещаться по массиву. У узла с индексом i левый потомок находится по индексу 2*i+1, а правый — по индексу 2*i+2. Потомок существует, только если его индекс находится в пределах массива и значение по этому индексу не равно -1. В массиве [3, 9, 6, -1, 2, 1, 7] у корня 3 потомки находятся по индексам 1 и 2, а у узла 9 с индексом 1 слева пустое место по индексу 3, а справа — узел 2 по индексу 4.

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

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

Алгоритм

Напишите 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, задача решена. В противном случае добавьте в стек его реальные дочерние узлы. В первом примере сначала извлекается правая сторона: листья 7 и 1 содержат суммы 16 и 10. Затем извлекается (1, 12) для узла 9. Это не лист, поэтому он добавляет в стек (4, 14) — лист с нужной суммой.

Каждый настоящий узел добавляется в стек один раз, поэтому время выполнения составляет 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. Сравнивай сумму только в листьях.
Считать пустое место для потомка концом пути. Если walk для пустого места возвращает remaining == 0, то 9 во втором примере считается листом из-за пустого левого места. Узел является листом, только если оба места пусты.
Забыть о корне как об отдельном случае. Единственный узел является листом, поэтому для [4] с targetSum = 4 результат — true, как и для [0] с targetSum = 0.
Прекращать поиск, как только сумма превысит целевое значение. В этой задаче значения никогда не бывают отрицательными, поэтому это безопасно, но тот же код начнёт давать неправильные ответы, как только дерево сможет содержать отрицательные значения.
Обращаться за пределы массива. У листа ближе к концу массива индексы потомков могут выходить за пределы последней записи, потому что массив может заканчиваться сразу после последнего узла. Проверь индекс, прежде чем читать tree[c].
Путать смещение в Lua и R, где индексация массивов начинается с 1. Оставляй индексы узлов 0-индексированными для арифметики 2*i+1, а считывай tree[i + 1].

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

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

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

Почему Path Sum проверяет сумму только в листовых узлах?

В задаче требуется путь от корня до листа, а путь, который заканчивается в узле с потомками, таким не является. Проверка в каждом узле слишком часто возвращает true, например, когда значение одного только корня равно целевому значению, но у корня есть потомок. Путь заканчивается в узле только тогда, когда оба его дочерних узла отсутствуют.

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

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

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

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

true