---
title: "DP на деревьях"
url: https://algopath.pro/ru/patterns/dp-on-trees
language: ru
summary: "Ответ каждого узла собирается из ответов его собственных потомков. Один обратный обход по дереву считает их все за проход."
updated: 2026-08-24
---

# DP на деревьях

Ответ каждого узла собирается из ответов его собственных потомков. Один обратный обход по дереву считает их все за проход.

## DP на деревьях: как это работает?

Решите, что один узел возвращает родителю. Часто это пара, по значению на каждый вариант.

Сначала спуститесь во всех потомков. До их ответа ничего решить нельзя.

Соберите ответ узла из ответов потомков. Эта сборка и есть переход.

Верните результат наверх. Больше родитель о поддереве ничего не знает.

Если ответ может лежать где угодно, ведите глобальный максимум при возврате. Одного корня не всегда хватает.

Один обратный обход касается каждого узла один раз. В этом вся стоимость.

- `лист возвращает (3, 0)` Грабим дома на дереве. Взять лист даёт 3, пропустить даёт 0.
- `узел 2 возвращает (2, 3)` Взять его и пропустить потомка либо пропустить и взять лучшее.
- `узел 3 возвращает (3, 1)` Его собственный потомок стоит всего 1.
- `корень взят = 3 + 3 + 1` Взятие корня заставляет пропустить обоих потомков.
- `ответ = 7` Семёрка бьёт шестёрку, которую даёт пропуск корня.

## DP на деревьях: когда применять?

- лучший выбор по иерархии или оргструктуре
- нельзя выбрать узел вместе с его прямым родителем
- постпорядок: дети решаются раньше родителя
- каждый узел объединяет состояния своих детей

## DP на деревьях: с чем путают?

- **Обход дерева** - Та страница про порядок посещения. Эта про то, что уносится наверх.
- **Динамическое программирование (1-D)** - У прямой одно направление, поэтому хватает индекса. Здесь порядок задаёт структура дерева.
- **Рекурсия с мемоизацией** - В дереве подзадачи не повторяются, поэтому кеш не нужен. Каждый узел посещается один раз.
- **Обход графа BFS / DFS** - В обычный граф можно попасть в узел дважды, и рекурсия может не кончиться. В дереве нельзя.

## DP на деревьях: сложность по времени и памяти

n узлов дают O(n), если в узле работы на O(1). Несколько состояний на узел это умножают.

## DP на деревьях: разбор примера

### Наибольшая сумма по любому пути

Верните наибольшую сумму по любому пути в двоичном дереве.

Путь может начинаться и кончаться где угодно, но не может ветвиться дважды.

Каждый узел возвращает лучший прямой путь, идущий вниз через него.

Отрицательная ветка отбрасывается. Лучший разветвлённый путь пишется в глобальный максимум при возврате.

```javascript
function maxPathSum(root) {
    let best = -Infinity;

    function down(node) {
        if (!node) return 0;

        // a negative branch is worse than taking nothing at all
        const left = Math.max(0, down(node.left));
        const right = Math.max(0, down(node.right));

        best = Math.max(best, node.val + left + right); // the fork stays local

        return node.val + Math.max(left, right); // the parent can only use one side
    }

    down(root);
    return best;
}
```

## DP на деревьях: частые ошибки

- **Возвращают то же, что и записывают** Наверх уходит прямой путь, а лучший ответ может ветвиться. Держите их раздельно.
- **Считают до ответа потомков** Переходу сначала нужны оба потомка. Сначала спуск, потом сборка.
- **Не разбирают случай пустого потомка** Узел с одним потомком всё равно вызывает вторую сторону. Верните там нейтральное значение.
- **Начинают максимум с нуля** Это прячет дерево, где все значения отрицательные. Начинайте с минус бесконечности.

## DP на деревьях: задачи с собеседований

- **Ограбление домов III** Два состояния на узел: взят или пропущен.
- **Максимальная сумма пути в дереве** Возвращается прямой путь, записывается разветвлённый.
- **Диаметр двоичного дерева** Глубина слева плюс глубина справа в каждом узле.
- **Самый длинный путь из равных значений** Продолжать можно только через равных потомков.
- **Распределение монет в дереве** Излишек передаётся наверх родителю.
- **Число хороших узлов** Максимум несут вниз, а не наверх.
- **Наклон дерева** Разность сумм двух поддеревьев.

## JavaScript

```javascript
function maxNonAdjacent(node) {
    if (!node) return [0, 0]; // [incl, excl]
    let inclSum = node.value;
    let exclSum = 0;
    for (const child of node.children) {
        const [inclC, exclC] = maxNonAdjacent(child);
        inclSum += exclC;
        exclSum += Math.max(inclC, exclC);
    }
    return [inclSum, exclSum];
}
```

## Python

```python
def max_non_adjacent(node):
    if node is None:
        return (0, 0)  # (incl, excl)
    incl_sum = node.value
    excl_sum = 0
    for child in node.children:
        incl_c, excl_c = max_non_adjacent(child)
        incl_sum += excl_c
        excl_sum += max(incl_c, excl_c)
    return (incl_sum, excl_sum)
```

## PHP

```php
function maxNonAdjacent(?Node $node): array {
    if ($node === null) return [0, 0]; // [incl, excl]
    $inclSum = $node->value;
    $exclSum = 0;
    foreach ($node->children as $child) {
        [$inclC, $exclC] = maxNonAdjacent($child);
        $inclSum += $exclC;
        $exclSum += max($inclC, $exclC);
    }
    return [$inclSum, $exclSum];
}
```