Бинарные деревья

На днях выкладывала статью на хабр по бинарным деревьям (с которой, видимо, тут собралось много народу). Подумала, не помешает краткий пост на эту же тему с основными поинтами, чтобы спустя время легко можно было освежить в памяти.

Итак, бинарные деревья - иерархические структура данных, в которой каждый узел имеет не более двух дочерних узлов (правый и левый потомки). Каждый потомок - тоже узел со своими потомками, если нет потомков у узла, то он называется листом.

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

Для решения алгоритмических задач на бинарные деревья преимущественно используется два способа:
- BFS (обход в ширину)
- DFS (обход в глубину)

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

Для обхода в ширину обычно используется очередь (Queue, а именно LinkedList), но лично я обхожусь списком (ArrayList) - тут можно дискутировать.

Пример задачи на обход в глубину:
Требуется обойти дерево в глубину прямым обходом (NLR) и вернуть последовательность узлов в виде списка.

Ссылка на задачу, как всегда

Рекурсивный способ:

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList();
    helper(root, result);
    return result;
}

private void helper(TreeNode root, List<Integer> result) {
    if (root != null) {
        result.add(root.val);
        helper(root.left, result);
        helper(root.right, result);
    }
}

Итеративный способ (с ArrayList, можете с ArrayDeque - тоже повод для дискуссии):

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
          return result;
    }

    List<TreeNode> stack = new ArrayList<>();
    stack.add(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.remove(stack.size() - 1);
        result.add(node.val);

        // Добавляем правого ребенка в стек первым, чтобы левый обрабатывался первым
        if (node.right != null) {
            stack.add(node.right);
        }
        if (node.left != null) {
            stack.add(node.left);
        }
    }

    return result;
}

Временная сложность: O(n) - в обоих случаях, т.к. обходим каждый узел один раз
Пространственная сложность - O(n) - в обоих случаях, т.к. размер итогового списка (result) будет зависеть от входного дерева.

Итеративный способ лучше использовать, если дерево слишком глубокое (для современных машинок более 1000 узлов можно считать глубоким), чтобы не увидеть StackOverFlow.

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

Полный текст статьи здесь: https://habr.com/ru/articles/835706/