Деревья: обходы и рекурсия

Суть

Бинарное дерево это узлы { val, left, right }. Большинство задач решается одной мыслью: что функция возвращает для поддерева и как ответ узла собирается из ответов детей.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

Как распознать приём по условию

• «глубина, диаметр, сбалансировано, сумма пути» → DFS post-order, ответ снизу вверх;
• «по уровням», «правый вид», «минимальная глубина», «ширина» → BFS с очередью;
• «проверь BST», «k-й наименьший» → in-order (в BST он отсортирован);
• «путь от корня с суммой», «сериализуй» → pre-order, передаём состояние сверху вниз;
• «общий предок» → в BST спуск по значениям, в обычном дереве post-order.

Шаблон DFS

function maxDepth(node) {
  if (!node) return 0;                       // база
  const l = maxDepth(node.left);
  const r = maxDepth(node.right);
  return 1 + Math.max(l, r);                 // сборка ответа
}

Передача состояния сверху вниз (границы BST):

function isBST(node, lo = -Infinity, hi = Infinity) {
  if (!node) return true;
  if (node.val <= lo || node.val >= hi) return false;
  return isBST(node.left, lo, node.val) && isBST(node.right, node.val, hi);
}

Шаблон BFS по уровням

function levels(root) {
  if (!root) return [];
  const res = [], queue = [root];
  let head = 0;                         // не shift: он O(n)
  while (head < queue.length) {
    const size = queue.length - head, level = [];
    for (let i = 0; i < size; i++) {
      const node = queue[head++];
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    res.push(level);
  }
  return res;
}

Сложность

Обход: O(n) времени. Память: DFS O(h) на стек (от log n до n), BFS O(ширина), до n/2 на последнем уровне. Поиск в BST O(h).

Ловушки

• Проверять BST только по детям.
• queue.shift() в BFS: O(n) на операцию, на больших деревьях O(n²).
• Путать «высота пустого дерева» 0 и -1: договорись в начале.
• Глубокая рекурсия на вырожденном дереве: переполнение стека, нужен итеративный вариант.
• Минимальная глубина: лист это узел без обоих детей, а не любой null.

Что спросят на собесе

• Обходы pre/in/post-order: чем отличаются, где используются?
• Проверь, что дерево является BST.
• Обход по уровням и его сложность по памяти.
• Найди наименьшего общего предка.
• Какая сложность поиска в BST и когда она деградирует?