Счёт вниз по дереву

Средняя

Дан корень root двоичного дерева с целыми числами в вершинах. Рассмотрим пути, которые начинаются в любой вершине и идут только вниз — от родителя к ребёнку. Путь подходит, если значение каждой следующей вершины ровно на 1 больше предыдущей, как при счёте 4, 5, 6, … Верните число вершин в самом длинном таком пути. Одна вершина — тоже путь длины 1.

Пример 1

root=tree_node([5, 6, 2, 7, 1, None, 3, None, None, None, None, None, 4]) → 3

Справа идёт 2 → 3 → 4, слева 5 → 6 → 7. Оба пути длиной 3, длиннее нет.

Пример 2

root=tree_node([3, 2, None, 1]) → 1

Числа вниз по дереву убывают, а нужен рост на единицу, поэтому лучший путь — одна вершина.

Пример 3

root=tree_node([1, None, 2, 4, None, 5]) → 2

Ограничения

1 ≤ число вершин ≤ 3·10⁴
-3·10⁴ ≤ Node.val ≤ 3·10⁴

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Tree Depth-First Search Binary Tree

Вход

root=tree_node([5, 6, 2, 7, 1, None, 3, None, None, None, None, None, 4])

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 94 теста на сервере, включая скрытые.