Invert Binary Tree

Лёгкая№226узлы дерева

Дан корень двоичного дерева. Нужно превратить его в зеркальное отражение: в каждом узле левый и правый потомки меняются местами, — и вернуть корень. Наше дерево: 6 с потомками 2 и 9; у 2 потомки 1 и 4, у 9 только правый потомок 8 — ответ: 6 с потомками 9 и 2; у 9 теперь только левый потомок 8, а у 2 потомки 4 и 1.

226 Invert Binary TreeРазбор · 1×

Пример: отразить двоичное дерево: каждый вызов сначала отражает оба поддерева, потом меняет местами своих двух потомков.

nonenonenonenonenonenonenone629148по порядку124698стек вызововвершина справа6
ещё не посещёнждёт в стеке вызововтекущий вызов и две стрелки, которые он меняет местамиотражён: потомки поменяныnone: пустой потомок

6 — узел, а не none

01/56
сначала · назад · пуск · шаг
Скорость
1function invert(node):
2 if node is none:
3 return none
4 left = invert(node.left)
5 right = invert(node.right)
6 node.left, node.right = right, left
7 return node
состояние
node
6
left
–
right
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Отражение дерева — это его корень, у которого слева отражение правого поддерева, а справа — отражение левого, поэтому каждому вызову нужны только ответы потомков и один обмен.
  2. Обмен переносит поддеревья целиком: когда меняется корень, 2 уходит вправо вместе с 4 и 1, которые поменялись раньше, так что ни один узел не меняется дважды.
  3. Каждый узел меняет местами своих потомков ровно один раз, пустых тоже, поэтому неотражённым ничего не остаётся.

Сложность

Время O(n): каждый узел посещаем один раз и делаем в нём один обмен. Память O(h), где h — высота дерева: в стеке вызовов лежит один путь.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.