Суть Прочитай четыре небольших сниппета про деревья — traversal, багованный валидатор BST, рекурсивную высоту и tree DP для суммы пути — и предскажи вывод или назови фикс с наибольшим рычагом.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небе
◷ 14 min
Баги в деревьях прячутся в порядке двух рекурсивных вызовов и в разнице между локальной проверкой и глобальной. Прочитай каждый сниппет, прогони его в голове и выбери, что внимательный инженер заключит или починит первым.
Цель
Потренируй главную петлю чтения кода деревьев: предскажи точный вывод traversal, заметь баг «на одно поддерево» в валидаторе BST, разбери базовый случай рекурсивной высоты и распознай, когда возвращаемое значение tree DP должно отличаться от ответа.
Какую точную последовательность это печатает и что это за traversal?
Heads-up Pre-order печатал бы node.value до рекурсии влево. Здесь console.log стоит между walk(node.left) и walk(node.right), поэтому левое поддерево печатается полностью раньше узла — это in-order, а не pre-order.
Heads-up Post-order печатает узел после обоих рекурсивных вызовов. Этот код печатает между двумя вызовами, поэтому 5 не последняя. Порядок in-order: 2, 3, 4, 5, 8, 9.
Heads-up Level-order требует очереди. Это рекурсия, то есть обход в глубину, поэтому breadth-first порядок по уровням она дать не может.
Сниппет 2 — баг валидатора BST
function isBST(node) { if (node === null) return true; if (node.left && node.left.value >= node.value) return false; if (node.right && node.right.value <= node.value) return false; return isBST(node.left) && isBST(node.right);}// 5// / \// 3 8// /// 4 // 4 < 5, но сидит в ПРАВОМ поддереве 5
Викторина
Completed
Этот валидатор возвращает true для дерева выше, которое НЕ является корректным BST. В чём баг?
Heads-up Строгость оператора влияет лишь на обработку дубликатов. Структурный баг остаётся: узел может пройти каждую проверку родитель-ребёнок и всё равно нарушить границу предка. Нужна передаваемая граница (min, max).
Heads-up Проверка через in-order — один из корректных фиксов, но заявленный баг конкретен: этот код валидирует только локальные пары родитель-ребёнок. Метод границы (min, max) прямо чинит эту логику.
Heads-up Пустое дерево — корректный BST, поэтому true верно. Изменение базового случая сломало бы корректные деревья и ничего не делает с отсутствующей границей предка.
Сниппет 3 — рекурсивная высота
function height(node) { if (node === null) return 0; // заметь: возвращает 0, не -1 return 1 + Math.max(height(node.left), height(node.right));}// одиночный листconsole.log(height(leaf));
Викторина
Completed
При базовом случае null, возвращающем 0, что печатает height(leaf) и какое соглашение это подразумевает?
Heads-up Функция прибавляет 1 за текущий узел перед возвратом, поэтому лист возвращает 1 + max(0, 0) = 1, а не 0. Ноль — это то, что возвращают его null-дети.
Heads-up Этот базовый случай возвращает 0, а не -1. -1 — сентинел для высоты в рёбрах; при 0 здесь получается высота в узлах, и лист равен 1.
Heads-up Math.max вызывается с двумя значениями: height(null) и height(null), каждое 0. Пустого вызова не происходит, поэтому он чисто возвращает 1.
Сниппет 4 — tree DP для суммы пути
function maxPathSum(root) { let best = -Infinity; function gain(node) { if (node === null) return 0; const left = Math.max(gain(node.left), 0); // отбросить отрицательные ветви const right = Math.max(gain(node.right), 0); best = Math.max(best, node.value + left + right); // путь ЧЕРЕЗ узел return node.value + Math.max(left, right); // путь, который родитель может продлить } gain(root); return best;}
Викторина
Completed
Почему gain() возвращает node.value + max(left, right), а best обновляется через node.value + left + right?
Heads-up Если бы gain возвращал left + right, родитель строил бы путь, который раздваивается в этом узле, а затем раздваивается ещё выше — это уже не простой путь. Путь входит в узел только с одной стороны, поэтому возврат вверх должен использовать одну ветвь.
Heads-up Зажимы лишь отбрасывают отрицательные ветви; они не делают формулы равными. Через узел (обе ветви) и продлеваемое вверх (одна ветвь) — действительно разные величины.
Heads-up best должен быть единым общим аккумулятором на весь обход, что и даёт переменная замыкания. Возврат его из gain смешал бы локальное возвращаемое значение с глобальным ответом — именно тот баг, которого паттерн избегает.
Итог
Чтение кода деревьев сводится к нескольким рефлексам: найди строку посещения относительно двух рекурсивных вызовов, чтобы назвать traversal (и помни, что in-order на BST отсортирован); никогда не доверяй валидатору BST, который проверяет только родитель-против-ребёнка — корректность требует передаваемой границы (min, max); читай базовый случай null, чтобы понять, считается ли высота в узлах (возврат 0) или в рёбрах (возврат -1); и в tree DP следи за намеренным разрывом между тем, что узел возвращает родителю (одна продлеваемая ветвь), и тем, что он вносит в глобальный ответ (полный изгиб через него).