Обход дерева

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

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

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

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

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

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

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

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

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;
}

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

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

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

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

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

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

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;
}

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

Эти формулировки в условии ведут сюда:

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

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

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

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

• Нет проверки на пустой узел

  Любая рекурсия обязана остановиться на пустом потомке. Эта проверка и есть базовый случай.

• Ставят посещение не туда

  Строка посещения это вся разница между порядками. Её перенос меняет ответ.

• Кладут потомков в неверном порядке

  Итеративный прямой обход кладёт сначала правого потомка. Стек переворачивает всё, что в него положили.

• Спускаются рекурсией по очень глубокому дереву

  Миллион узлов в одной цепочке переполняет стек вызовов. Там нужен явный стек.

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

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

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

O(n)

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