Диаметр дерева: два BFS, рекурсия с высотами и центр дерева

Как найти диаметр дерева за O(n): два обхода BFS/DFS и почему они работают, рекурсия с высотами, Diameter of Binary Tree, взвешенные деревья и поиск центра дерева. Код на Python.

14 мин чтенияалгоритмы · деревья · графы · python

Коротко

Что ищемСпособСложность
Диаметр невзвешенного дереваДва BFS/DFSO(n)O(n) / O(n)O(n)
Диаметр + сам путьДва BFS с массивом родителейO(n)O(n) / O(n)O(n)
Diameter of Binary Tree (LC 543)Рекурсия: высота слева + справаO(n)O(n) / O(h)O(h)
Диаметр с весами ≥0\ge 0Два DFS с суммой весовO(n)O(n) / O(n)O(n)
Диаметр с отрицательными весамиТолько ДП с двумя лучшими веткамиO(n)O(n) / O(n)O(n)
Центр дерева (Minimum Height Trees)Середина диаметра или обрезка листьевO(n)O(n) / O(n)O(n)

Диаметр дерева — длина самого длинного простого пути между двумя вершинами. Длину обычно считают в рёбрах (или в сумме весов, если дерево взвешенное). Главная идея всех решений: в дереве между двумя вершинами ровно один путь, поэтому самый длинный путь можно найти за линейное время, без перебора всех пар.

Наивное решение и почему оно плохое

Первое, что приходит в голову: запустить BFS из каждой вершины, найти самую дальнюю и взять максимум. Это правильно, но стоит O(n2)O(n^2): nn обходов по O(n)O(n) каждый. Для дерева на 10510^5 вершин это 101010^{10} операций — тайм-аут гарантирован.

Брутфорс всё равно полезен: им удобно проверять быстрые решения на случайных деревьях. Все примеры кода в этой статье прогнаны против него.

Способ 1: два обхода

Алгоритм помещается в две строки:

  1. Из любой вершины ss найти самую дальнюю вершину aa.
  2. Из aa найти самую дальнюю вершину bb. Расстояние a→ba \to b — диаметр.

Для невзвешенного дерева подходит и 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. Самая дальняя — a=6a = 6.
  • BFS из вершины 6: 5→1, 2→2, 4→3, 1→3, 3→4, 7→5. Самая дальняя — b=7b = 7, расстояние 5.
  • Путь 7 – 3 – 1 – 2 – 5 – 6, диаметр 5 рёбер.

Почему это работает

Ключевое утверждение: самая дальняя вершина от любой точки дерева — конец какого-то диаметра. Набросок доказательства.

Пусть uu–vv — настоящий диаметр, а aa — самая дальняя вершина от ss. Предположим, aa не является концом никакого диаметра.

  • Если путь s→as \to a пересекается с путём u→vu \to v в какой-то вершине xx, то d(x,a)≥d(x,v)d(x, a) \ge d(x, v) (иначе vv была бы дальше от ss, чем aa). Тогда путь u→x→au \to x \to a не короче u→vu \to v, то есть тоже диаметр — противоречие.
  • Если пути не пересекаются, соединим их кратчайшим путём p→qp \to q (pp на пути s→as \to a, qq на пути u→vu \to v). Из того, что aa самая дальняя от ss, следует d(p,a)≥d(p,q)+d(q,v)d(p, a) \ge d(p, q) + d(q, v). Тогда путь u→q→p→au \to q \to p \to a длиннее u→vu \to v — снова противоречие.

Значит, aa — конец диаметра, и второй обход от aa находит второй конец. Это рассуждение использует только то, что длины рёбер неотрицательны — запомните, это пригодится ниже.

Сложность: два обхода — O(n)O(n) по времени и памяти.

Способ 2: рекурсия с высотами

Второй подход — через динамическое программирование на деревьях. Подвесим дерево за любую вершину. Каждый простой путь имеет самую высокую вершину — ту, что ближе всего к корню. В ней путь «перегибается»: спускается в два разных поддерева (или в одно, если вершина — конец пути).

Значит, для каждой вершины vv достаточно знать две самые большие высоты её детей:

best(v)=h1+h2,hi=height(childi)+1\text{best}(v) = h_1 + h_2, \quad h_i = \text{height}(\text{child}_i) + 1

где h1≥h2h_1 \ge h_2 — две наибольшие глубины спуска из vv. Диаметр — максимум best(v)\text{best}(v) по всем вершинам. Высоты считаются тем же обходом, снизу вверх.

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 — корень можно выбрать любой

Функция возвращает одно (высоту), а ответ копит в отдельной переменной. Это главный трюк задач «путь в дереве»: возвращаемое значение и ответ — разные вещи. Родителю нужен только самый длинный луч вниз, а путь через вершину считается на месте и наверх не передаётся.

Итеративная версия

На дереве-«бамбуке» из 2⋅1052 \cdot 10^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. Смешивать эти соглашения — главный источник ошибок на единицу.

Сложность: O(n)O(n) по времени, O(h)O(h) по памяти на стек рекурсии, где hh — высота дерева. Обход здесь — обычный 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).

Факты, которые стоит знать:

  • центр всегда лежит на любом диаметре, ровно посередине;
  • центров один (если диаметр DD чётный) или два соседних (если нечётный);
  • радиус R=⌈D/2⌉R = \lceil D / 2 \rceil.

Отсюда первый способ: найти путь-диаметр двумя 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, а не «пока есть листья», — принципиально: при двух оставшихся вершинах обе — листья, и их нельзя снимать.

Центр ≠ центроид

Частая путаница. Центр минимизирует максимальное расстояние до остальных вершин. Центроид минимизирует размер самого большого поддерева после удаления вершины. На «метле» — длинной ручке, к концу которой прикреплено много листьев, — центр находится посередине ручки, а центроид — у основания пучка листьев. Центроиды нужны для центроидной декомпозиции, центр — для задач про минимальную высоту и «где поставить сервер, чтобы самый дальний клиент был ближе всего».

Типичные ошибки

  1. Считать, что диаметр проходит через корень. В LC 543 ответ часто лежит целиком в одном поддереве. Поэтому обновляем best в каждом узле, а не только в корне.
  2. Путаница рёбер и вершин. Диаметр в рёбрах = число вершин на пути − 1. Решите заранее, что возвращает height(None), и держитесь этого соглашения.
  3. Возвращать из рекурсии путь, а не луч. Родителю нельзя отдавать left + right — путь с перегибом не продолжить вверх.
  4. Две BFS при отрицательных весах. Работает только при весах ≥0\ge 0. Иначе — ДП.
  5. Одна BFS из корня. Дальняя от корня вершина — лишь один конец диаметра; без второго обхода ответ будет высотой, а не диаметром.
  6. Рекурсия на глубоком дереве в Python. Бамбук на 10510^5 вершин гарантированно уронит рекурсивное решение. Либо итеративный обход, либо sys.setrecursionlimit вместе с увеличением стека потока.
  7. Обрезка листьев до пустого графа. Остановитесь, когда осталось ≤ 2 вершин, и не забудьте про n=1n = 1.

Где встречается на собеседованиях

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

Итог

  • Невзвешенное дерево или веса ≥0\ge 0: два обхода, O(n)O(n), заодно получаем сам путь и центр.
  • Бинарное дерево на собеседовании: рекурсия с высотами, ответ копится в отдельной переменной.
  • Отрицательные веса: только ДП с двумя лучшими ветками.
  • Центр — середина любого диаметра; радиус ⌈D/2⌉\lceil D/2 \rceil; в LC 310 — обрезка листьев слоями.

Потренироваться в спокойной обстановке

Все задачи