Почему это работает
- Прямой обход начинается с корня, а в симметричном корень стоит между левым и правым поддеревьями: один взгляд в pos делит диапазон на два поддерева.
- Прямой обход перечисляет всё левое поддерево раньше правого, поэтому, если строить сначала левое, значения берутся ровно по порядку: next идёт только вперёд.
- Каждая половина — та же задача на меньшем диапазоне, её строит та же функция; пустой диапазон — пустое поддерево.
Сложность
Время O(n): каждое значение один раз становится узлом, а pos находит его место за O(1). Память O(n): в pos все значения, а стек вызовов глубиной в высоту дерева.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗