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