Алгоритмы с нуля

Динамическое программирование на деревьях

Суть Узел возвращает одно вверх (высоту), отслеживая другое в боковой переменной (диаметр). Классический пример: самый длинный путь между двумя узлами в двоичном дереве. Одно решение, два ответа, один проход.

◷ 28 min

Вы решали задачи на деревьях, спрашивая оба поддерева о значении и комбинируя ответы. Но что если финальный ответ НЕ тот, что вы возвращаете? Что если узел должен возвратить свою высоту родителю, но вычислить что-то ещё — например, самый длинный путь через него — и положить то в боковую переменную? Это динамическое программирование на деревьях: рекурсивный вызов узла отвечает на один вопрос (возврат вверх), в то время как глобальная или боковая переменная отслеживает другой вопрос (актуальный ответ). Классический пример — диаметр двоичного дерева, самый длинный путь между любыми двумя узлами, где каждый узел возвращает свою высоту но отслеживает самый длинный путь, проходящий через него.

Цель

После этого урока вы сможете реализовать рекурсивные функции на деревьях, где возвращаемое значение отличается от финального ответа, узнать и применить паттерн DP на деревьях (постпорядковая рекурсия + боковая переменная), решить задачу диаметра двоичного дерева и трассировать её правильно, реализовать проверку, что дерево высотно-сбалансировано, предсказать и проверить временную и пространственную сложность алгоритмов DP на деревьях, и расширить паттерн на вариации (самый длинный путь с суммой, диаметр в направленных деревьях).

Идея

Что такое DP на деревьях (динамическое программирование на деревьях)?

DP на деревьях — техника, где рекурсивная функция на дереве решает две задачи одновременно:

Возвращаемое значение (отправляется вверх к родителю).
Боковое вычисление (отслеживается глобально или в изменяемой переменной).

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

Паттерн

function treeDp(node) {
  // Базовый случай
  if (node is null) return baseValue;
  
  // Рекурсируй на поддеревья
  leftInfo = treeDp(node.left);
  rightInfo = treeDp(node.right);
  
  // Комбинируй для возврата (отправляется вверх)
  returnValue = combine(leftInfo, rightInfo, node);
  
  // Обнови боковой ответ (глобальный ответ)
  globalAnswer = updateAnswer(globalAnswer, leftInfo, rightInfo, node);
  
  return returnValue;
}

На каждом узле:

Рекурсируй вниз на оба поддерева (постпорядок).
Вычисли возвращаемое значение, которое имеет смысл для родителя (например, высота).
Обнови боковую переменную с финальным ответом (например, самый длинный путь).

Пример: диаметр двоичного дерева

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

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

Но чтобы ответить на этот вопрос для каждого узла, мы должны возвратить что-то другое родителю: высоту поддерева. Итак:

Возвращаем: высота поддерева.
Боковая переменная: самый длинный путь, найденный пока (диаметр).

Диаметр в узле

Для узла с высотой левого поддерева lh и высотой правого поддерева rh:

Самый длинный путь через узел = lh + rh + 2 (в рёбрах). (Значение +2 учитывает рёбра от узла вниз к прямым детям.)
Высота поддерева, укоренённого в узле = 1 + max(lh, rh).

Соглашение о высоте

Листовой узел (без детей) имеет высоту 0. Пустое поддерево (null) имеет высоту -1. Это делает математику рабочей: узел с двумя пустыми детьми возвращает 1 + max(-1, -1) = 0, что правильно для листа.

Код

Пример 1: Диаметр двоичного дерева


      1
      function diameterOfBinaryTree(root) {
    

      2
      let maxDiameter = 0;
    

      3
       
    

      4
      function dfs(node) {
    

      5
        // Базовый случай: пустое поддерево имеет высоту -1
    

      6
        if (node === null) return -1;
    

      7
        
    

      8
        // Рекурсируй на оба поддерева
    

      9
        const leftHeight = dfs(node.left);
    

      10
        const rightHeight = dfs(node.right);
    

      11
        
    

      12
        // Обнови глобальный ответ:
    

      13
        // Самый длинный путь через этот узел (в рёбрах)
    

      14
        const diameterThroughNode = leftHeight + rightHeight + 2;
    

      15
        maxDiameter = Math.max(maxDiameter, diameterThroughNode);
    

      16
        
    

      17
        // Возврати высоту этого поддерева (отправляется родителю)
    

      18
        return 1 + Math.max(leftHeight, rightHeight);
    

      19
      }
    

      20
       
    

      21
      dfs(root);
    

      22
      return maxDiameter;
    

      23
      }

L1 Функция вычисляет диаметр (самый длинный путь в рёбрах) дерева.
L2 Боковая переменная: отслеживает самый длинный путь, найденный пока.
L5 Базовый случай: пустое поддерево имеет высоту -1 (делает математику чистой).
L8 Рекурсируй влево: получи высоту левого поддерева.
L9 Рекурсируй вправо: получи высоту правого поддерева.
L12 Самый длинный путь через ЭТОТ узел — (высота левая) + (высота правая) + 2 ребра.
L13 Обнови боковую переменную: помни самый длинный путь, видимый где-либо в дереве.
L16 Возврати высоту этого поддерева (то, что нужно родителю для решения его задачи).

Пример: Для дерева:

Структура дерева:

Узел 1 — корень.
Узел 1’s левое поддерево (укоренённое в 2) и правое поддерево (укоренённое в 3).
Узел 2’s левое поддерево (укоренённое в 4, лист) и правое поддерево (укоренённое в 5, лист).

Высоты (лист = 0, null = -1):

Узел 4 (лист): высота = 0
Узел 5 (лист): высота = 0
Узел 3 (лист): высота = 0
Узел 2 (два ребёнка): высота = 1 + max(0, 0) = 1
Узел 1 (два ребёнка): высота = 1 + max(1, 0) = 2

Диаметры (самый длинный путь через каждый узел):

Узел 4: диаметр = -1 + -1 + 2 = 0 (лист, путь — просто сам себя)
Узел 5: диаметр = -1 + -1 + 2 = 0 (лист, путь — просто сам себя)
Узел 3: диаметр = -1 + -1 + 2 = 0 (лист, путь — просто сам себя)
Узел 2: диаметр = 0 + 0 + 2 = 2 (путь от 4 → 2 → 5 — 2 ребра)
Узел 1: диаметр = 1 + 0 + 2 = 3 (путь от 4 → 2 → 1 → 3 — 3 ребра)

Самый длинный путь во всём дереве — 3 ребра: 4 → 2 → 1 → 3.

Пример 2: Высотно-сбалансированное двоичное дерево

Дерево высотно-сбалансировано, если для каждого узла высоты левого и правого поддеревьев отличаются не более чем на 1. Мы можем проверить это с помощью DP на деревьях: возвращаем высоту если сбалансировано, или -1 как сентинель для «несбалансировано».


      1
      function isBalanced(root) {
    

      2
      function dfs(node) {
    

      3
        // Базовый случай: пустое поддерево сбалансировано с высотой -1
    

      4
        if (node === null) return -1;
    

      5
        
    

      6
        // Рекурсируй на левое поддерево
    

      7
        const leftHeight = dfs(node.left);
    

      8
        // Если левое несбалансировано, распространи сентинель -1
    

      9
        if (leftHeight === -1) return -1;
    

      10
        
    

      11
        // Рекурсируй на правое поддерево
    

      12
        const rightHeight = dfs(node.right);
    

      13
        // Если правое несбалансировано, распространи сентинель -1
    

      14
        if (rightHeight === -1) return -1;
    

      15
        
    

      16
        // Проверь, сбалансирован ли этот узел
    

      17
        if (Math.abs(leftHeight - rightHeight) > 1) {
    

      18
          return -1; // Не сбалансировано
    

      19
        }
    

      20
        
    

      21
        // Возврати высоту этого поддерева
    

      22
        return 1 + Math.max(leftHeight, rightHeight);
    

      23
      }
    

      24
       
    

      25
      return dfs(root) !== -1; // true если высота была вычислена, false если -1 (несбалансировано)
    

      26
      }

L1 Функция проверяет, высотно-сбалансировано ли дерево, и возвращает true/false.
L3 Базовый случай: пустое дерево сбалансировано с высотой -1.
L6 Рекурсируй влево; получи высоту (или -1 если несбалансировано).
L8 Проверка сентинеля: если левое поддерево несбалансировано, распространи -1 вверх.
L11 Рекурсируй вправо; получи высоту (или -1 если несбалансировано).
L13 Проверка сентинеля: если правое поддерево несбалансировано, распространи -1 вверх.
L16 Если абсолютная разница высот больше 1, этот узел несбалансирован.
L17 Возврати -1 (сентинель) чтобы распространить несбалансированное состояние вверх.
L21 Возврати высоту этого поддерева (финальный ответ для родителя).
L24 Если dfs(root) не -1, дерево сбалансировано.

Пример: Для дерева:

Узел 4 (лист): высота = 0, сбалансирован.
Узел 3 (лист): высота = 0, сбалансирован.
Узел 2 (левый ребёнок 4, нет правого): высота = 0, высота левого = 0, высота правого = -1. Разница = |0 - (-1)| = 1 ≤ 1, сбалансирован. Возвращает высоту 1.
Узел 1 (левый ребёнок 2, правый ребёнок 3): высота левого = 1, высота правого = 0. Разница = |1 - 0| = 1 ≤ 1, сбалансирован. Возвращает высоту 2.

Результат: isBalanced(root) = true.

Запусти оба на конкретных деревьях

class Node {
constructor(value, left = null, right = null) {
  this.value = value;
  this.left = left;
  this.right = right;
}
}

// Функция диаметра
function diameterOfBinaryTree(root) {
let maxDiameter = 0;

function dfs(node) {
  if (node === null) return -1;
  const leftHeight = dfs(node.left);
  const rightHeight = dfs(node.right);
  const diameterThroughNode = leftHeight + rightHeight + 2;
  maxDiameter = Math.max(maxDiameter, diameterThroughNode);
  return 1 + Math.max(leftHeight, rightHeight);
}

dfs(root);
return maxDiameter;
}

// Функция проверки сбалансированности
function isBalanced(root) {
function dfs(node) {
  if (node === null) return -1;
  const leftHeight = dfs(node.left);
  if (leftHeight === -1) return -1;
  const rightHeight = dfs(node.right);
  if (rightHeight === -1) return -1;
  if (Math.abs(leftHeight - rightHeight) > 1) return -1;
  return 1 + Math.max(leftHeight, rightHeight);
}
return dfs(root) !== -1;
}

// Построй дерево:
//      1
//     / \
//    2   3
//   / \
//  4   5

let node4 = new Node(4);
let node5 = new Node(5);
let node2 = new Node(2, node4, node5);
let node3 = new Node(3);
let root = new Node(1, node2, node3);

console.log("Диаметр:", diameterOfBinaryTree(root));
console.log("Сбалансировано:", isBalanced(root));

Output

Пошаговый разбор


      1
      let root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3));
    

      2
      diameterOfBinaryTree(root);

Сложность

Временная сложность

Алгоритмы DP на деревьях посещают каждый узел ровно один раз. На каждом узле мы выполняем O(1) работу (сравнения, арифметика, обновления переменных). Так как есть n узлов, общее время — O(n).

Пространственная сложность

Оба алгоритма используют рекурсию, поэтому глубина стека вызовов равна высоте дерева. В худшем случае (вырожденное дерево) высота — O(n). В сбалансированном дереве высота — O(log n).

Таким образом, пространственная сложность — O(h), где h — высота дерева.

Практика 0 / 5

В паттерне DP на деревьях, что узел возвращает своему родителю?

Для дерева с такой структурой, какой диаметр (в рёбрах)? ``` 1 / 2 / 3 ```

Почему сентинельное значение (как -1) полезно в проверке высотно-сбалансированного дерева?

В алгоритме диаметра, почему базовый случай возвращает -1 (не 0)?

Которая из этих НЕ задача DP на деревьях (где возвращаемое значение ≠ финальный ответ)?

lesson.inset.undefined

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

lesson.inset.undefined

Путница: смешивание возвращаемого значения с ответом. Новички часто думают, что возвращаемое значение — ЭТО финальный ответ. Но в DP на деревьях, возвращаемое значение — локальная информация (высота), и финальный ответ — в боковой переменной (диаметр). Возвращаемое значение — то, что нужно родителю; боковая переменная — то, что вы пришли найти. Держи их отдельно.

lesson.inset.undefined

Краевой случай: дерево с одним узлом. Если дерево — просто один узел, диаметр — 0 (самый длинный путь — сам узел, ноль рёбер). С нашим соглашением о высоте (null = -1, лист = 0), вычисление диаметра даёт 0 + 0 + 2 = 2, что неправильно! Исправление: учти это, начиная maxDiameter с 0 и убеждаясь, что вычисление диаметра правильно захватывает единый узел. Наш код делает это: единственный узел’s диаметр = (-1) + (-1) + 2 = 0. Это правильно! Единственный узел имеет диаметр 0 рёбер (путь — просто сам себя).

Проверь себя

Викторина

Объясни паттерн DP на деревьях: что такое возвращаемое значение против боковой переменной, и почему этот паттерн решает сложные задачи на деревьях за один проход?

Итог

Динамическое программирование на деревьях комбинирует рекурсию с боковой переменной для решения задач на деревьях за один проход. Паттерн: каждый узел возвращает локальную информацию (как высоту) своему родителю, в то время как обновляет боковую переменную с глобальным ответом (как диаметр). Классический пример — диаметр двоичного дерева, самый длинный путь между любыми двумя узлами. Проверка высотно-сбалансированного дерева использует сентинельное значение (-1) чтобы кодировать и высоту и статус сбалансированности в одном возвращаемом значении. DP на деревьях — необходимо для сложных задач на деревьях: это избегает множественных проходов и обнаруживает элегантную, двух-частную структуру решения. Дальше: Раздел 08 охватывает кучи и приоритетные очереди, другой способ организовать данные для быстрого доступа к минимальному (или максимальному) элементу.

Продолжить восхождение ↑Деревья: тест с выбором ответа