Почему это работает
- Две стороны зеркальны ровно тогда, когда равны их корни, левый потомок левой стороны зеркален правому потомку правой, а правый потомок левой — левому потомку правой.
- Поэтому пары перекрещиваются: 5 с левого края встречается с 5 с правого — это внешняя пара, а 7 с 9 у середины — внутренняя. Узел никогда не сравнивается с тем, что стоит на том же месте под другой 6.
- Первая несовпавшая пара сразу возвращает false наверх, поэтому остальное не сравниваем.
Сложность
Время O(n): каждый узел попадает не больше чем в одну пару, и каждую пару сравниваем один раз. Память O(h), где h — высота дерева: в стеке вызовов лежит один путь из пар.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗