Маршрут по дереву

Средняя

Дан корень root двоичного дерева из n вершин; все значения вершин различны. Также даны значения двух разных вершин этого дерева: start и finish. Опишите кратчайший путь от вершины start до вершины finish строкой из букв: - 'L' — перейти в левого ребёнка; - 'R' — перейти в правого ребёнка; - 'U' — подняться к родителю. Верните эту строку.

Пример 1

root=tree_node([4, 2, 6, 1, 3, 5]), start=3, finish=5 → 'UURL'

Путь 3 → 2 → 4 → 6 → 5: два шага вверх, потом вправо и влево.

Пример 2

root=tree_node([1, None, 2]), start=1, finish=2 → 'R'

Вершина 2 — правый ребёнок корня.

Пример 3

root=tree_node([3, 1, 2]), start=2, finish=3 → 'U'

Ограничения

2 ≤ n ≤ 10⁵
1 ≤ значение вершины ≤ 10⁵, значения не повторяются
Вершины start и finish есть в дереве
start ≠ finish

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

Решили0

Пробовали0

Отправок0

Принято—

Темы

Tree Depth-First Search String Binary Tree

Вход

root=tree_node([4, 2, 6, 1, 3, 5]), start=3, finish=5

Ожидается

'UURL'

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