Шаблон решения задач на бинарные деревья. Tree Traversal

Решил сделать цикл коротких постов с шаблонами решения основных типов алгоритмических задач с собеседований.

Если в условии у вас бинарное дерево, то в подавляющем числе случаев вам нужно применить алгоритм обхода дерева: DFS или BFS. Наиболее часто нужно применять DFS. Для бинарного дерева он упрощается до:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    visit(node);
    traverse(node.right);
}

visit - это ваша кастомная логика, которая будет специфична для конкретной задачи. Ее можно поместить до рекурсивных вызовов для левого и правого ребенка. В таком случае такой обход дерева называется pre-order tree traversal:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    visit(node);
    traverse(node.left);
    traverse(node.right);
}

Между рекурсивными вызовами, в таком случае такой обход называется in-order tree traversal:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    visit(node);
    traverse(node.right);
}

и после рекурсивных вызовов, такой обход называется post-order tree traversal:

void traverse(TreeNode node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    traverse(node.right); 
    visit(node);
}

Особенностью in-order tree traversal является то, что для BST (бинарного дерева поиска), метод visit будет вызываться для вершин дерева в порядке возрастания значений.

Во многих задачах, вам нужно будет что-то вычислять во время обхода дерева. Обычно, это min/max от различных значений. Для этого вам нужно будет расширить метод обхода и дополнить его параметрами и возвращаемыми значениями:

int traverse(TreeNode node) {
    if (node == null) {
        return {base_value};
    }
    int leftResult = traverse(node.left);
    int rightResult = traverse(node.right); 
    return {f(leftResult, rightResult, node.value)};
}

{base_value} - значение для базового случая (для листа дерева). Обычно, это 0 или 1.
{f(leftResult, rightResult, node.value)} - какая-то функция от результатов для левого, правого поддерева и значения в текущей вершине. Обычно это min/max от суммы, разницы и т.д.

Иногда нужно передавать какие-то параметры:

int traverse(TreeNode node, int value) {
    if (node == null) {
        return {base_value};
    }
    int leftResult = traverse(node.left, {foo(value)});
    int rightResult = traverse(node.right, {bar(value)}); 
    return {f(leftResult, rightResult, node.value)};
}

{foo(value)}, {bar(value)} - какие-то функции от value. Часто это value + 1 или value -1. Но зависит от задачи. Иногда это какие-то более сложные функции, которые могут зависеть от текущего значения в вершине: node.value.

Иногда вам нужно сокращать область поиска (особенно для BST(бинарного дерева поиска)) или делать дополнительные проверки перед рекурсивным вызовом:

int traverse(TreeNode node, int value) {
    if (node == null) {
        return {base_value};
    }
    int leftResult = 0;
    if ({left_condition}) {
        leftResult = traverse(node.left, {foo(value)});
    }
    int rightResult = 0;
    if ({right_condition}) {
        traverse(node.right, {bar(value)}); 
    }
    return {f(leftResult, rightResult, node.value)};
}

{left_condition}, {right_condition} - обычно зависят от node.value. Условия вроде node.value > value, node.value < value.