Диаметр дерева: два BFS, рекурсия с высотами и центр дерева
Как найти диаметр дерева за O(n): два обхода BFS/DFS и почему они работают, рекурсия с высотами, Diameter of Binary Tree, взвешенные деревья и поиск центра дерева. Код на Python.
Коротко
| Что ищем | Способ | Сложность |
|---|---|---|
| Диаметр невзвешенного дерева | Два BFS/DFS | / |
| Диаметр + сам путь | Два BFS с массивом родителей | / |
| Diameter of Binary Tree (LC 543) | Рекурсия: высота слева + справа | / |
| Диаметр с весами | Два DFS с суммой весов | / |
| Диаметр с отрицательными весами | Только ДП с двумя лучшими ветками | / |
| Центр дерева (Minimum Height Trees) | Середина диаметра или обрезка листьев | / |
Диаметр дерева — длина самого длинного простого пути между двумя вершинами. Длину обычно считают в рёбрах (или в сумме весов, если дерево взвешенное). Главная идея всех решений: в дереве между двумя вершинами ровно один путь, поэтому самый длинный путь можно найти за линейное время, без перебора всех пар.
Наивное решение и почему оно плохое
Первое, что приходит в голову: запустить BFS из каждой вершины, найти самую дальнюю и взять максимум. Это правильно, но стоит : обходов по каждый. Для дерева на вершин это операций — тайм-аут гарантирован.
Брутфорс всё равно полезен: им удобно проверять быстрые решения на случайных деревьях. Все примеры кода в этой статье прогнаны против него.
Способ 1: два обхода
Алгоритм помещается в две строки:
- Из любой вершины найти самую дальнюю вершину .
- Из найти самую дальнюю вершину . Расстояние — диаметр.
Для невзвешенного дерева подходит и BFS, и DFS: в дереве путь до вершины единственный, поэтому любой обход посчитает расстояния правильно. Возьмём BFS — заодно сохраним родителей, чтобы восстановить сам путь.
from collections import deque def bfs(graph, start): dist = {start: 0} parent = {start: None} queue = deque([start]) while queue: v = queue.popleft() for u in graph[v]: if u not in dist: dist[u] = dist[v] + 1 parent[u] = v queue.append(u) far = max(dist, key=dist.get) return far, dist[far], parent def diameter_two_bfs(graph): a, _, _ = bfs(graph, next(iter(graph))) b, length, parent = bfs(graph, a) path = [] while b is not None: path.append(b) b = parent[b] return length, path def build(edges): graph = {} for a, b in edges: graph.setdefault(a, []).append(b) graph.setdefault(b, []).append(a) return graph edges = [(1, 2), (1, 3), (2, 4), (2, 5), (5, 6), (3, 7)] graph = build(edges) print(diameter_two_bfs(graph)) # (5, [7, 3, 1, 2, 5, 6])
Разбор на примере
1
/ \
2 3
/ \ \
4 5 7
|
6
- BFS из вершины 1: расстояния
2→1, 3→1, 4→2, 5→2, 7→2, 6→3. Самая дальняя — . - BFS из вершины 6:
5→1, 2→2, 4→3, 1→3, 3→4, 7→5. Самая дальняя — , расстояние 5. - Путь
7 – 3 – 1 – 2 – 5 – 6, диаметр 5 рёбер.
Почему это работает
Ключевое утверждение: самая дальняя вершина от любой точки дерева — конец какого-то диаметра. Набросок доказательства.
Пусть – — настоящий диаметр, а — самая дальняя вершина от . Предположим, не является концом никакого диаметра.
- Если путь пересекается с путём в какой-то вершине , то (иначе была бы дальше от , чем ). Тогда путь не короче , то есть тоже диаметр — противоречие.
- Если пути не пересекаются, соединим их кратчайшим путём ( на пути , на пути ). Из того, что самая дальняя от , следует . Тогда путь длиннее — снова противоречие.
Значит, — конец диаметра, и второй обход от находит второй конец. Это рассуждение использует только то, что длины рёбер неотрицательны — запомните, это пригодится ниже.
Сложность: два обхода — по времени и памяти.
Способ 2: рекурсия с высотами
Второй подход — через динамическое программирование на деревьях. Подвесим дерево за любую вершину. Каждый простой путь имеет самую высокую вершину — ту, что ближе всего к корню. В ней путь «перегибается»: спускается в два разных поддерева (или в одно, если вершина — конец пути).
Значит, для каждой вершины достаточно знать две самые большие высоты её детей:
где — две наибольшие глубины спуска из . Диаметр — максимум по всем вершинам. Высоты считаются тем же обходом, снизу вверх.
def diameter_heights(graph, root): best = 0 def height(v, parent): nonlocal best top1 = top2 = 0 for u in graph[v]: if u == parent: continue h = height(u, v) + 1 if h > top1: top1, top2 = h, top1 elif h > top2: top2 = h best = max(best, top1 + top2) return top1 height(root, None) return best print(diameter_heights(graph, 1)) # 5 print(diameter_heights(graph, 7)) # 5 — корень можно выбрать любой
Функция возвращает одно (высоту), а ответ копит в отдельной переменной. Это главный трюк задач «путь в дереве»: возвращаемое значение и ответ — разные вещи. Родителю нужен только самый длинный луч вниз, а путь через вершину считается на месте и наверх не передаётся.
Итеративная версия
На дереве-«бамбуке» из вершин рекурсия в Python упадёт с RecursionError (лимит по умолчанию — 1000). Сначала обходим дерево стеком и запоминаем порядок, потом идём по нему в обратную сторону — дети гарантированно обработаны раньше родителей.
def diameter_iterative(graph, root): order, parent = [], {root: None} stack = [root] while stack: v = stack.pop() order.append(v) for u in graph[v]: if u != parent[v]: parent[u] = v stack.append(u) height = {} best = 0 for v in reversed(order): top1 = top2 = 0 for u in graph[v]: if u != parent[v]: h = height[u] + 1 if h > top1: top1, top2 = h, top1 elif h > top2: top2 = h height[v] = top1 best = max(best, top1 + top2) return best bamboo = build([(i, i + 1) for i in range(1, 200_000)]) print(diameter_iterative(bamboo, 1)) # 199999
Подробнее о том, как развернуть рекурсию в стек, — в статье про рекурсию.
Diameter of Binary Tree (LeetCode 543)
Самая частая форма задачи на собеседованиях. Дан корень бинарного дерева, нужно вернуть длину самого длинного пути в рёбрах. Путь не обязан проходить через корень.
Это ровно способ 2, только детей не больше двух, и выбирать «две лучшие» не нужно — берём левую и правую высоты целиком.
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def diameterOfBinaryTree(self, root): self.best = 0 def height(node): if node is None: return 0 left = height(node.left) right = height(node.right) self.best = max(self.best, left + right) return 1 + max(left, right) height(root) return self.best root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3)) print(Solution().diameterOfBinaryTree(root)) # 3: путь 4-2-1-3
Здесь height(None) = 0, а высота листа равна 1 — это число вершин на самом длинном луче вниз. Поэтому left + right — это как раз число рёбер пути через узел: от левого поддерева до узла left рёбер, от узла до правого — right. Если удобнее считать высоту в рёбрах (лист = 0, None = −1), формула превратится в left + right + 2. Смешивать эти соглашения — главный источник ошибок на единицу.
Сложность: по времени, по памяти на стек рекурсии, где — высота дерева. Обход здесь — обычный post-order из статьи про обходы бинарного дерева.
Родственные задачи
Тот же шаблон «вернуть луч, обновить ответ путём через узел» решает целое семейство:
- Binary Tree Maximum Path Sum (LC 124) — вместо высот суммы значений; отрицательные лучи обрезаются до нуля:
max(0, gain(child)). - Longest Univalue Path (LC 687) — луч продолжается, только если значение ребёнка совпадает с текущим.
- Balanced Binary Tree (LC 110) — та же рекурсия по высотам, только вместо суммы проверяем разницу.
Если освоить LC 543, остальные решаются заменой пары строк. Больше похожих задач — в подборке задач на деревья.
Взвешенные деревья
Когда у рёбер есть длины, диаметр — максимальная сумма весов на пути. BFS тут больше не считает расстояния «по слоям», но в дереве это и не нужно: путь до каждой вершины единственный, так что любой обход, который прибавляет вес ребра, даёт правильное расстояние.
def farthest(graph, start): dist = {start: 0} stack = [start] while stack: v = stack.pop() for u, w in graph[v]: if u not in dist: dist[u] = dist[v] + w stack.append(u) far = max(dist, key=dist.get) return far, dist[far] def weighted_diameter(graph): a, _ = farthest(graph, next(iter(graph))) _, length = farthest(graph, a) return length def wbuild(edges): graph = {} for a, b, w in edges: graph.setdefault(a, []).append((b, w)) graph.setdefault(b, []).append((a, w)) return graph g = wbuild([(1, 2, 3), (2, 3, 4), (2, 4, 10), (1, 5, 2)]) print(weighted_diameter(g)) # 15: путь 4-2-1-5
Никакого Дейкстры не требуется — она нужна графам с несколькими путями между вершинами, а в дереве выбирать не из чего.
Ловушка: отрицательные веса
Доказательство корректности двух обходов опиралось на неотрицательность весов. С отрицательными рёбрами метод ломается:
neg = wbuild([(1, 2, 5), (2, 3, -100), (3, 4, 50)]) print(weighted_diameter(neg)) # 5 — неверно!
Из вершины 1 самая дальняя — 2 (расстояние 5), из 2 тоже ничего дальше пяти нет. А настоящий ответ — 50: ребро 3–4 само по себе. Первый обход «не видит» его, потому что дорога туда проходит через ребро с весом −100.
ДП с двумя лучшими ветками работает при любых весах: оно рассматривает каждую вершину как точку перегиба и не делает предположений о том, где лежит конец диаметра.
def weighted_diameter_dp(graph, root): order, parent = [], {root: None} stack = [root] while stack: v = stack.pop() order.append(v) for u, _ in graph[v]: if u != parent[v]: parent[u] = v stack.append(u) down = {} best = 0 for v in reversed(order): top1 = top2 = 0 # 0 = «не спускаться вниз вообще» for u, w in graph[v]: if u != parent[v]: h = down[u] + w if h > top1: top1, top2 = h, top1 elif h > top2: top2 = h down[v] = top1 best = max(best, top1 + top2) return best print(weighted_diameter_dp(g, 1)) # 15 print(weighted_diameter_dp(neg, 1)) # 50
Нули в top1 = top2 = 0 важны: они означают, что луч может закончиться прямо в вершине, а не тащить за собой отрицательную ветку. Ровно та же идея, что max(0, gain) в LC 124. Если по условию путь обязан содержать хотя бы одно ребро, ответ нужно инициализировать иначе — уточните это у интервьюера.
Центр дерева
Эксцентриситет вершины — расстояние до самой дальней от неё вершины. Центр — вершина (или вершины) с минимальным эксцентриситетом, а этот минимум называют радиусом. Если подвесить дерево за центр, его высота будет минимальной — это задача Minimum Height Trees (LC 310).
Факты, которые стоит знать:
- центр всегда лежит на любом диаметре, ровно посередине;
- центров один (если диаметр чётный) или два соседних (если нечётный);
- радиус .
Отсюда первый способ: найти путь-диаметр двумя BFS и взять середину.
def tree_center(graph): length, path = diameter_two_bfs(graph) if length % 2 == 0: return [path[length // 2]] return [path[length // 2], path[length // 2 + 1]] print(tree_center(graph)) # [1, 2]: диаметр 7-3-1-2-5-6 нечётной длины 5
Обрезка листьев
Второй способ — тот, что обычно ждут в LC 310. Снимаем все листья слоем, потом новые листья, и так пока не останется одна или две вершины. Это похоже на топологическую сортировку по Кану, только «входящую степень» заменяет обычная степень вершины.
def find_min_height_trees(n, edges): if n == 1: return [0] graph = [[] for _ in range(n)] for a, b in edges: graph[a].append(b) graph[b].append(a) degree = [len(nei) for nei in graph] leaves = [v for v in range(n) if degree[v] == 1] remaining = n while remaining > 2: remaining -= len(leaves) next_leaves = [] for leaf in leaves: for u in graph[leaf]: degree[u] -= 1 if degree[u] == 1: next_leaves.append(u) leaves = next_leaves return leaves print(find_min_height_trees(4, [[1, 0], [1, 2], [1, 3]])) # [1] print(find_min_height_trees(6, [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]])) # [3, 4]
Почему работает: каждый слой листьев укорачивает каждый диаметр на одно ребро с обоих концов, а середина диаметра остаётся на месте. Когда осталось не больше двух вершин, это и есть середина. Условие remaining > 2, а не «пока есть листья», — принципиально: при двух оставшихся вершинах обе — листья, и их нельзя снимать.
Центр ≠ центроид
Частая путаница. Центр минимизирует максимальное расстояние до остальных вершин. Центроид минимизирует размер самого большого поддерева после удаления вершины. На «метле» — длинной ручке, к концу которой прикреплено много листьев, — центр находится посередине ручки, а центроид — у основания пучка листьев. Центроиды нужны для центроидной декомпозиции, центр — для задач про минимальную высоту и «где поставить сервер, чтобы самый дальний клиент был ближе всего».
Типичные ошибки
- Считать, что диаметр проходит через корень. В LC 543 ответ часто лежит целиком в одном поддереве. Поэтому обновляем
bestв каждом узле, а не только в корне. - Путаница рёбер и вершин. Диаметр в рёбрах = число вершин на пути − 1. Решите заранее, что возвращает
height(None), и держитесь этого соглашения. - Возвращать из рекурсии путь, а не луч. Родителю нельзя отдавать
left + right— путь с перегибом не продолжить вверх. - Две BFS при отрицательных весах. Работает только при весах . Иначе — ДП.
- Одна BFS из корня. Дальняя от корня вершина — лишь один конец диаметра; без второго обхода ответ будет высотой, а не диаметром.
- Рекурсия на глубоком дереве в Python. Бамбук на вершин гарантированно уронит рекурсивное решение. Либо итеративный обход, либо
sys.setrecursionlimitвместе с увеличением стека потока. - Обрезка листьев до пустого графа. Остановитесь, когда осталось ≤ 2 вершин, и не забудьте про .
Где встречается на собеседованиях
- LC 543 Diameter of Binary Tree — классика уровня Easy, часто как разминка перед LC 124. Интервьюер почти всегда спросит, почему путь не обязательно через корень.
- LC 1245 Tree Diameter — тот же вопрос для произвольного дерева, заданного списком рёбер; хорошо показывает, знаете ли вы двойной BFS.
- LC 310 Minimum Height Trees — центр дерева через обрезку листьев.
- LC 124 Binary Tree Maximum Path Sum — Hard, но по сути диаметр с весами в вершинах и отрицательными значениями.
- Follow-up вопросы: «восстановите сам путь», «а если веса отрицательные?», «а если дерево очень глубокое?», «докажите, что два BFS дают правильный ответ».
Если хотите освежить базу обходов перед этими задачами, загляните в статью про DFS и BFS.
Итог
- Невзвешенное дерево или веса : два обхода, , заодно получаем сам путь и центр.
- Бинарное дерево на собеседовании: рекурсия с высотами, ответ копится в отдельной переменной.
- Отрицательные веса: только ДП с двумя лучшими ветками.
- Центр — середина любого диаметра; радиус ; в LC 310 — обрезка листьев слоями.