BFS по уровням и выбор BFS/DFS

Для дерева 1(2,3) очередь начинается как [1]: снимаем ровно один узел и добавляем 2,3; следующий зафиксированный размер 2 даёт второй уровень [2,3].

Как собрать значения дерева по уровням?

Вернуть значения бинарного дерева как список уровней.

Определение глубины каждого узла отдельным проходом

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

Почему повторный поиск каждого уровня лишний?

Верхние узлы повторно посещаются для каждого уровня, что в цепочке даёт O(n²).

Размер очереди фиксирует текущий слой

FIFO-очередь обрабатывает родителей раньше детей; количество элементов в начале уровня сообщает, сколько узлов относится к нему.

Что лежит в очереди перед началом уровня?

Перед внутренним циклом очередь содержит ровно все узлы текущего уровня слева направо.

Снимаем levelSize узлов и добавляем их детей

Положить корень в queue. Пока queue не пуста, запомнить size, извлечь ровно size узлов в новый level и добавить их детей в конец.

Обход по уровням на C++17 и Python 3

C++17

#include <cassert>
#include <queue>
#include <vector>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;
};

vector<vector<int>> levelOrder(Node* root) {
    if (root == nullptr) return {};
    queue<Node*> pending;
    pending.push(root);
    vector<vector<int>> levels;
    while (!pending.empty()) {
        int levelSize = static_cast<int>(pending.size());
        vector<int> level;
        for (int i = 0; i < levelSize; ++i) {
            Node* node = pending.front();
            pending.pop();
            level.push_back(node->value);
            if (node->left) pending.push(node->left);
            if (node->right) pending.push(node->right);
        }
        levels.push_back(level);
    }
    return levels;
}

int main() {
    Node left{2, nullptr, nullptr};
    Node right{3, nullptr, nullptr};
    Node root{1, &left, &right};
    assert((levelOrder(&root) == vector<vector<int>>{{1}, {2, 3}}));
    assert(levelOrder(nullptr).empty());
}

Python 3

from collections import deque


class Node:
    def __init__(
        self,
        value: int,
        left: "Node | None" = None,
        right: "Node | None" = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def level_order(root: Node | None) -> list[list[int]]:
    if root is None:
        return []
    pending = deque([root])
    levels: list[list[int]] = []
    while pending:
        level: list[int] = []
        for _ in range(len(pending)):
            node = pending.popleft()
            level.append(node.value)
            if node.left is not None:
                pending.append(node.left)
            if node.right is not None:
                pending.append(node.right)
        levels.append(level)
    return levels


assert level_order(Node(1, Node(2), Node(3))) == [[1], [2, 3]]
assert level_order(None) == []

O(w) для очереди и O(n) для возвращаемых уровней

O(n) времени. Вспомогательная очередь занимает O(w), где w — максимальная ширина дерева; возвращаемые уровни отдельно занимают O(n), потому что содержат каждое значение.

Пустое дерево, цепочка и широкий слой

Пустое дерево; один узел; цепочка; широкий последний уровень. Null-дети в очередь не добавляются.

Тесты на границы между уровнями

null -> []; 1 -> [[1]]; 1(2,3) -> [[1],[2,3]]; несимметричное дерево.

Когда в условии важны расстояние или слой?

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

Когда DFS проще и экономнее по ширине?

Если нужно агрегировать поддерево снизу вверх, postorder DFS обычно естественнее и экономит очередь.

Мини-проверка: зачем сохранять размер очереди?

Вопрос: почему size читается до добавления детей? Ответ: иначе дети текущего уровня ошибочно попадут в тот же level.

Мини-проверка: всегда ли память BFS равна O(h)?

Вопрос: память BFS всегда O(h)? Ответ: нет, она зависит от ширины; у полного дерева последний уровень может содержать O(n) узлов.

Проведите очередь через дерево 1(2,3)

Проследите очередь для дерева 1(2(4,5),3) и покажите её содержимое до каждого уровня.

Найдите среднее значение каждого уровня

Задача 1

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

Размер очереди отделяет один слой от следующего

BFS отделяет уровни снимком размера очереди до того, как туда добавятся дети.