---
title: "Обход дерева"
url: https://algopath.pro/ru/patterns/tree-traversal
language: ru
summary: "Обойдите каждый узел дерева ровно один раз. Именно то, в каком месте вы посещаете узел, и решает, что в итоге вычислит обход."
updated: 2026-08-24
---

# Обход дерева

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

## Обход дерева: как это работает?

Любой обход делает в узле одно и то же. Он посещает узел и спускается в каждого потомка.

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

Симметричный обход идёт влево, потом узел, потом вправо. На дереве поиска это даёт отсортированный порядок.

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

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

Меняется только место посещения. Сам проход во всех вариантах одинаков.

- `корень 1, потомки 2 и 3` Корень достигается первым при любом порядке.
- `прямой: 1, 2, 3` Сначала записывается узел, потом оба потомка.
- `симметричный: 2, 1, 3` Левый потомок записывается раньше самого узла.
- `обратный: 2, 3, 1` Оба потомка завершаются до записи узла.
- `по уровням: 1, 2, 3` Очередь читает ряд за рядом, а не вглубь.

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

- бинарное дерево задано как корневой узел с указателями left/right
- посетить каждый узел (прямой / симметричный / обратный / по уровням)
- посчитать глубину, высоту или сумму по всему дереву
- обработать детей до или после родителя
- вывод по уровням (BFS с очередью)

## Обход дерева: с чем путают?

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

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

n узлов дают O(n) времени. Память O(h) на стек, а h равно n на вырожденной цепочке.

## Обход дерева: разбор примера

### Диаметр двоичного дерева

Верните самый длинный путь между любыми двумя узлами, считая в рёбрах.

Путь не обязан проходить через корень.

В любом узле лучший локальный путь это глубина слева плюс глубина справа.

Значит считайте глубину обратным обходом. Лучшую сумму запоминайте при возврате.

```javascript
function diameterOfBinaryTree(root) {
    let best = 0;

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

        const left = depth(node.left);
        const right = depth(node.right);

        // the path passing through this node, counted in edges
        best = Math.max(best, left + right);

        return 1 + Math.max(left, right);
    }

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

## Обход дерева: частые ошибки

- **Нет проверки на пустой узел** Любая рекурсия обязана остановиться на пустом потомке. Эта проверка и есть базовый случай.
- **Ставят посещение не туда** Строка посещения это вся разница между порядками. Её перенос меняет ответ.
- **Кладут потомков в неверном порядке** Итеративный прямой обход кладёт сначала правого потомка. Стек переворачивает всё, что в него положили.
- **Спускаются рекурсией по очень глубокому дереву** Миллион узлов в одной цепочке переполняет стек вызовов. Там нужен явный стек.

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

- **Симметричный обход дерева** Чистая форма, рекурсией или через стек.
- **Глубина двоичного дерева** Единица плюс более глубокий из двух потомков.
- **Диаметр двоичного дерева** Глубина слева плюс глубина справа в каждом узле.
- **Обход дерева по уровням** Очередь, по одному ряду за раунд.
- **Сумма на пути** Несите накопленную сумму вниз по дереву.
- **Зеркальное отражение дерева** Поменяйте местами двух потомков в каждом узле.
- **Вид дерева справа** Последний узел, достигнутый на каждом уровне.

## JavaScript

```javascript
function traverse(node, result = []) {
    if (!node) return result; // base case
    traverse(node.left, result);
    result.push(node.val); // inorder here; move this line for pre/post
    traverse(node.right, result);
    return result;
}
```

## Python

```python
def traverse(node, result=None):
    if result is None:
        result = []
    if not node:
        return result
    traverse(node.left, result)
    result.append(node.val)  # inorder here; move this line for pre/post
    traverse(node.right, result)
    return result
```

## PHP

```php
function traverse(?TreeNode $node, array &$result = []): array {
    if ($node === null) return $result;
    traverse($node->left, $result);
    $result[] = $node->val; // inorder here; move this line for pre/post
    traverse($node->right, $result);
    return $result;
}
```