0Pricing
Coding Interview Prep · Урок

Диаметр, высота и сбалансированные деревья

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

«Диаметр, высота и сбалансированные деревья» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Высота двоичного дерева

height (или максимальная глубина) двоичного дерева — это длина самого длинного пути от корня до любого листа. Она вычисляется рекурсивно: height любого узла равна 1 + max(height(left), height(right)), а для пустых узлов базовый случай равен 0. Это вычисление в порядке снизу вверх является фундаментальным: высота служит основой для диаметра, проверки сбалансированности и вращений в деревьях AVL.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root))  # 4

Диаметр: самый длинный путь

Диаметр двоичного дерева — это длина самого длинного пути между любыми двумя узлами; этот путь может проходить через корень, а может и не проходить. Длина пути измеряется в рёбрах. Для любого узла диаметр, проходящий через него, равен height(left) + height(right). Общий диаметр — максимальное из таких значений для всех узлов дерева.

def diameter_of_binary_tree(root):
    max_diameter = [0]  # use list to allow closure mutation

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Diameter through this node
        max_diameter[0] = max(max_diameter[0], left_h + right_h)
        return 1 + max(left_h, right_h)  # height for parent

    dfs(root)
    return max_diameter[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root))  # 3

Один проход DFS для вычисления диаметра

Наивный подход вызывает height() в каждом узле, что даёт сложность O(n²) для сбалансированного дерева. Оптимальное решение вычисляет высоту и обновляет диаметр за один проход DFS. Ключевая идея заключается в том, что рекурсивная функция dfs() одновременно выполняет две задачи: возвращает высоту родителю и побочным эффектом обновляет глобальный максимальный диаметр. Этот шаблон обратного обхода с двойной целью встречается во многих задачах о деревьях.

# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
    if not root:
        return 0
    through_root = height(root.left) + height(root.right)
    in_left = diameter_naive(root.left)
    in_right = diameter_naive(root.right)
    return max(through_root, in_left, in_right)

# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')

Проверка сбалансированности двоичного дерева

Двоичное дерево является сбалансированным по высоте, если высоты левого и правого поддеревьев каждого узла отличаются не более чем на единицу. Наивный подход вызывает height() в каждом узле, что даёт сложность O(n²). Оптимальный подход использует тот же приём с одним проходом: возвращайте -1 как специальный признак «дерево несбалансировано» и передавайте его вверх, прекращая обход сразу после обнаружения несбалансированного узла.

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1:
            return -1  # propagate early exit
        right = check(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1  # unbalanced here
        return 1 + max(left, right)  # height if balanced

    return check(root) != -1

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5)  # too deep on left
print(is_balanced(root))  # False

Шаблон со специальным возвращаемым значением

Возврат специального значения (-1 для несбалансированного дерева или особого кортежа) — распространённый шаблон, когда вспомогательной функции DFS нужно сообщить два вида информации: вычисленный результат и факт нарушения ограничения. Вместо создания исключений или использования глобальных флагов закодируйте ошибку в типе возвращаемого значения. Такой подход прост, не использует глобальное состояние и естественно сочетается с другими рекурсивными вспомогательными функциями.

# General pattern: return (is_valid, computed_value)
def balanced_height(node):
    if not node:
        return True, 0
    left_ok, left_h = balanced_height(node.left)
    if not left_ok:
        return False, 0  # short-circuit
    right_ok, right_h = balanced_height(node.right)
    if not right_ok:
        return False, 0
    balanced = abs(left_h - right_h) <= 1
    return balanced, 1 + max(left_h, right_h)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h)  # True 2

Диаметр в узлах и рёбрах

Внимательно читайте условие задачи: LeetCode №543 измеряет диаметр в рёбрах, тогда как в некоторых задачах измерение ведётся в узлах. Если нужно посчитать узлы, диаметр через некоторый узел равен height(left) + height(right) + 1 — единица добавляется за сам узел. Если нужно посчитать рёбра, единицу добавлять не следует. Всегда уточняйте это у интервьюера до начала написания кода.

def diameter_in_nodes(root):
    max_path = [0]

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Path through this node in NODE count
        nodes_through = left_h + right_h + 1
        max_path[0] = max(max_path[0], nodes_through)
        return 1 + max(left_h, right_h)

    dfs(root)
    return max_path[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root))  # 4 nodes: 4-2-1-3 or 5-2-1-3

Сумма пути: любой путь от корня до листа

В задаче о сумме пути спрашивается: существует ли путь от корня до листа, сумма значений на котором равна целевому значению? Используйте DFS и при спуске вычитайте значение текущего узла из целевого значения. В листе проверьте, равно ли оставшееся целевое значение значению этого листа. Это прямой обход DFS, в котором оставшаяся сумма передаётся как параметр, — классический пример нисходящей рекурсии.

def has_path_sum(root, target):
    if not root:
        return False
    # Leaf node: check if we've exactly hit the target
    if not root.left and not root.right:
        return root.val == target
    remaining = target - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

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=22

Максимальная сумма пути: сложный вариант

Максимальная сумма пути (LeetCode №124) значительно сложнее: путь может начинаться и заканчиваться в любых узлах, а не только идти от корня к листу, и значения могут быть отрицательными. В каждом узле рассмотрите четыре варианта: только сам узел, узел с ветвью слева, узел с ветвью справа или узел с обеими ветвями. Только первые три варианта могут продолжаться вверх к родителю; четвёртый является конечным кандидатом на глобальный максимум.

def max_path_sum(root):
    max_sum = [float('-inf')]

    def gain(node):
        if not node:
            return 0
        # Only take positive contributions
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        # Best path through this node (can't go both ways upward)
        max_sum[0] = max(max_sum[0], node.val + left + right)
        # Return the best single-branch gain for parent
        return node.val + max(left, right)

    gain(root)
    return max_sum[0]

root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root))  # 42: 15+20+7

Деревья AVL и самобалансировка

Дерево AVL — это BST, поддерживающее свойство сбалансированности по высоте с помощью вращений после операций вставки и удаления. Каждый узел хранит коэффициент балансировки — разность высот правого и левого поддеревьев, — который должен оставаться в пределах {-1, 0, 1}. При нарушении баланса одинарное или двойное вращение восстанавливает его за O(1) времени, сохраняя общую высоту на уровне O(log n) и гарантируя сложность всех операций O(log n).

# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node

# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root

# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')

Проверка симметричности дерева

Двоичное дерево является симметричным, если оно представляет собой собственное зеркальное отражение. Рекурсивная проверка заключается в следующем: дерево симметрично, если для каждой пары соответствующих узлов по разные стороны оси их значения равны, а поддеревья являются зеркальными отражениями друг друга. Определите вспомогательную функцию is_mirror(left, right), которая проверяет: оба узла пусты — всё в порядке, один узел пуст — условие не выполнено, значения равны, а внутренние и внешние поддеревья являются зеркальными отражениями.

def is_symmetric(root):
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)

sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym))  # True

nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym))  # False

Объединение сведений о высоте и диаметре

Шаблон однопроходного обхода в постпорядке, при котором вспомогательная функция одновременно возвращает высоту и обновляет глобальный результат, применим во множестве задач: вычислении диаметра, максимальной суммы пути, проверке сбалансированности, подсчёте хороших узлов и других. Всегда спрашивайте: «Какая информация нужна родителю от каждого потомка?» Это возвращаемое значение. «Какие вычисления относятся непосредственно к этому узлу?» Они обновляют глобальный ответ. Такое разбиение — ключевой навык для решения сложных задач на деревьях.

# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
    result = [float('-inf')]  # or 0 depending on problem

    def dfs(node):
        if not node:
            return 0  # base return (height, count, etc.)
        left_val = dfs(node.left)
        right_val = dfs(node.right)
        # --- Update global result using both children ---
        candidate = left_val + right_val  # example: diameter
        result[0] = max(result[0], candidate)
        # --- Return info needed by PARENT ---
        return 1 + max(left_val, right_val)  # example: height

    dfs(root)
    return result[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root))  # diameter = 2

Быстрая проверка

Проверьте своё понимание концепций курса «Структуры данных & алгоритмы — подготовка к собеседованию по программированию», рассмотренных в этом уроке.

Итоги урока

В этом уроке Вы изучили: вычисление высоты с помощью рекурсивного обхода DFS в постпорядке, вычисление диаметра за один проход O(n) с помощью вспомогательной функции DFS двойного назначения и проверку сбалансированности с использованием специального значения для досрочного завершения. Далее мы рассмотрим задачи на сумму пути и наименьшего общего предка.

Часто задаваемые вопросы

Урок «Диаметр, высота и сбалансированные деревья» бесплатный?

Да — полный текст урока «Диаметр, высота и сбалансированные деревья» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Диаметр, высота и сбалансированные деревья»?

Вычисляйте диаметр и высоту дерева за один проход DFS с помощью вспомогательной функции, возвращающей оба значения, а затем проверяйте сбалансированность дерева по высоте Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Диаметр, высота и сбалансированные деревья»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Класс TreeNode и обход BFS по уровням
  2. DFS: симметричный, прямой и обратный обход
  3. Диаметр, высота и сбалансированные деревья
  4. Сумма путей и наименьший общий предок
← Назад к Coding Interview Prep