DFS дерева: что возвращает рекурсия

В цепочке 1→2→3 узел 3 возвращает высоту 1, узел 2 — 2, корень — 3; каждый родитель использует только два ответа детей.

Как вычислить высоту дерева снизу вверх?

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

Пересчёт глубины для каждого пути от корня

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

Почему одни поддеревья нельзя обходить повторно?

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

Родителю достаточно высот двух детей

Родителю нужны только две величины: высота левого и правого поддеревьев.

Что возвращает вызов height для каждого поддерева?

height(node) возвращает точную высоту поддерева node; для null высота равна 0.

База null и объединение двух ответов

Рекурсивно получить leftHeight и rightHeight, вернуть 1 + max(...). База null возвращает 0.

Высота дерева на C++17 и Python 3

C++17

#include <algorithm>
#include <cassert>
using namespace std;

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

int height(Node* node) {
    if (node == nullptr) return 0;
    return 1 + max(height(node->left), height(node->right));
}

int main() {
    Node leaf{3, nullptr, nullptr};
    Node child{2, &leaf, nullptr};
    Node root{1, &child, nullptr};
    assert(height(&root) == 3);
    assert(height(nullptr) == 0);
}

Python 3

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 height(node: Node | None) -> int:
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


assert height(Node(1, Node(2, Node(3)))) == 3
assert height(None) == 0

Один визит на узел и стек глубины h

O(n) времени и O(h) стека. В Python глубокая цепочка может превысить лимит рекурсии; итеративный BFS/DFS избегает этого.

Пустое дерево, лист и несбалансированная цепочка

Пустое дерево -> 0; один узел -> 1; только одна ветвь; две ветви разной глубины.

Тесты на разные формы дерева

null, один узел, полное дерево высоты 2, цепочка из четырёх узлов.

Сигнал: ответ родителя складывается из ответов детей

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

Когда глобальное состояние только мешает?

Не используйте глобальную переменную, если задача естественно возвращает значение; глобальное состояние усложняет повторные вызовы.

Мини-проверка: почему height(null) равна нулю?

Вопрос: почему база null равна 0? Ответ: тогда лист получает 1+max(0,0)=1, что соответствует определению.

Мини-проверка: высота в узлах или в рёбрах?

Вопрос: что изменится при высоте в рёбрах? Ответ: базу часто задают -1 или отдельно определяют пустое дерево; определение должно быть единым.

Подпишите возвраты от листьев к корню

Для дерева высот поддеревьев 2 и 4 вычислите возврат корня и подпишите возврат каждого листа.

Проверьте баланс дерева одним DFS

Задача 1

Для каждого узла вычислите, сбалансировано ли его поддерево по высоте, не пересчитывая высоты повторно.

Хороший DFS возвращает родителю ровно нужное резюме

Сначала одним предложением определите возвращаемое значение; переход и база должны прямо следовать из этого определения.