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