Сумма путей и наименьший общий предок
Решайте задачи о сумме пути от корня к листу, сумме всех путей и наименьшем общем предке в произвольном двоичном дереве с помощью рекурсивного спуска
«Сумма путей и наименьший общий предок» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Сумма пути от корня до листа
Задача о сумме пути спрашивает, существует ли путь от корня до листа, сумма значений на котором равна целевой. Передавайте оставшуюся целевую сумму вниз по рекурсии, вычитая значение каждого узла. В листе проверьте, равна ли оставшаяся сумма значению листа. Это избавляет от необходимости хранить явный список пути и одновременно экономит память и упрощает решение. Особый случай: у пустого дерева нет путей, поэтому сразу верните False.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5->4->11->2Все пути от корня до листа
Чтобы перечислить все пути, поддерживайте список текущего пути. При каждом рекурсивном вызове добавляйте значение текущего узла, рекурсивно обрабатывайте потомков, а затем при возврате выполняйте pop (возврат шага). В листе сохраните снимок (list(path)) текущего пути. Этот шаблон — выбрать, рекурсивно обработать, отменить выбор — лежит в основе возврата с возвратом шага при работе с деревьями.
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]Сумма пути III: любой путь, любые узлы
Сумма пути III (LeetCode #437) подсчитывает пути, сумма которых равна целевой, причём путь может начинаться и заканчиваться где угодно, а не только в корне и листе. Решение полным перебором занимает O(n²): запустите DFS из каждого узла. Оптимальный подход за O(n) использует хеш-таблицу префиксных сумм: отслеживайте текущую сумму и подсчитывайте, сколько раз ранее встречалось значение current_sum - target, по аналогии с подходом для суммы подмассивов.
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3Что такое наименьший общий предок?
Наименьший общий предок (LCA) двух узлов p и q в бинарном дереве — это наиболее глубокий узел, потомками которого являются и p, и q; при этом узел может быть потомком самого себя. LCA используется в таких задачах, как «расстояние между двумя узлами», «путь между двумя узлами» и запросы диапазона в BST. Понимание LCA необходимо для решения задач среднего уровня на деревьях.
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')Рекурсивный алгоритм LCA
Элегантное рекурсивное решение для LCA возвращает первый узел, который является либо p, либо q, либо имеет оба этих узла в своих поддеревьях. Если текущий узел — p или q, верните его. В противном случае рекурсивно обработайте левое и правое поддеревья. Если обе стороны возвращают непустой результат, текущий узел — это LCA. Если непустой результат возвращает только одна сторона, передайте его вверх. Время работы — O(n), а дополнительная память — O(h).
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3LCA, когда узел может быть собственным предком
Критически важный особый случай: если p является предком q или наоборот, LCA — это сам p. Рекурсивный алгоритм обрабатывает этот случай автоматически: достигнув p, он сразу возвращает p, не просматривая поддеревья p. Родитель увидит, что одна сторона вернула p, а другая — пустое значение, и передаст p вверх как LCA. При написании LCA всегда проверяйте этот случай с помощью теста.
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)LCA с указателями на родителей
Если у каждого узла есть указатель на родителя, задача поиска LCA сводится к задаче о «пересечении двух связных списков». Соберите предков p в множество, затем поднимайтесь от q вверх, пока не найдёте узел, входящий в это множество. Такой подход со временем работы O(h) и дополнительной памятью O(h) часто встречается на собеседованиях по проектированию систем, когда Вы управляете структурой узла и можете хранить ссылки на родителей.
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')LCA в бинарном дереве поиска
В BST поиск LCA проще, поскольку свойство упорядоченности подсказывает, в каком поддереве находится каждый узел. Если и p, и q меньше текущего узла, LCA находится в левом поддереве. Если оба больше, LCA находится в правом поддереве. В противном случае текущий узел разделяет их, поэтому он и есть LCA. Для сбалансированных BST это уменьшает сложность задачи до O(log n).
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
print('BST LCA: O(log n) for balanced trees')Расстояние между двумя узлами
Расстояние между двумя узлами в дереве равно числу рёбер на соединяющем их пути. Его можно напрямую вычислить через LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Сначала найдите LCA, затем вычислите глубину каждого узла. С подходящей вспомогательной функцией это выполняется за O(n) времени и с дополнительной памятью O(h).
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2Путь от корня до листа с максимальной суммой
Путь от корня до листа с максимальной суммой отслеживает текущую сумму от корня до текущего узла. В листьях сравнивайте её с глобальным максимумом. Это обход DFS в прямом порядке, при котором сумма текущего пути передаётся как параметр. В отличие от общей задачи о максимальной сумме пути, этот вариант ограничен путями от корня до листа и потому проще: не нужно рассматривать произвольные пути от одного узла к другому.
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8Сумма чисел от корня до листа
Сумма чисел от корня до листа (LeetCode #129) рассматривает каждый путь от корня до листа как десятичное число, например путь 1→2→3 представляет число 123, и просит найти сумму этих чисел. Формируйте число, передавая вниз по рекурсии значение current_number * 10 + node.val. В каждом листе добавляйте полученное число к общей сумме. Это наглядный пример обхода DFS в прямом порядке с передачей накопленного состояния вниз.
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026Быстрая проверка
Проверьте своё понимание концепций курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию», рассмотренных в этом уроке.
Итоги урока
В этом уроке Вы изучили: варианты задач на сумму пути — от корня до листа, все пути и сумму пути III с префиксными суммами, наименьшего общего предка с использованием элегантного рекурсивного разделения и LCA в BST за O(log n) благодаря свойству упорядоченности. Далее мы начнём изучать бинарные деревья поиска: операции вставки и поиска.
Часто задаваемые вопросы
Урок «Сумма путей и наименьший общий предок» бесплатный?
Да — полный текст урока «Сумма путей и наименьший общий предок» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Сумма путей и наименьший общий предок»?
Решайте задачи о сумме пути от корня к листу, сумме всех путей и наименьшем общем предке в произвольном двоичном дереве с помощью рекурсивного спуска Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Сумма путей и наименьший общий предок»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Класс TreeNode и обход BFS по уровням
- DFS: симметричный, прямой и обратный обход
- Диаметр, высота и сбалансированные деревья
- Сумма путей и наименьший общий предок