Symmetric Tree

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

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

101 Symmetric TreeРазбор · 1×

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

nonenonenonenonenonenonenonenone8665795стек вызовов mirror, вершина справаa, слева—b, справа—
ещё не сравнивалипара ждёт в стеке вызововпара, которую сравниваемпара вернула trueпара вернула falsenone: пустой потомок

Сгибаем дерево по середине: сравниваем две половины под 8, mirror(6, 6)

01/21
сначала · назад · пуск · шаг
Скорость
1function isSymmetric(root):
2 return mirror(root.left, root.right)
3
4function mirror(a, b):
5 if a is none and b is none:
6 return true
7 if a is none or b is none or a.val != b.val:
8 return false
9 if not mirror(a.left, b.right):
10 return false
11 return mirror(a.right, b.left)
состояние
a
–
b
–
нажмите шаг, чтобы вернуться

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

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

  1. Две стороны зеркальны ровно тогда, когда равны их корни, левый потомок левой стороны зеркален правому потомку правой, а правый потомок левой — левому потомку правой.
  2. Поэтому пары перекрещиваются: 5 с левого края встречается с 5 с правого — это внешняя пара, а 7 с 9 у середины — внутренняя. Узел никогда не сравнивается с тем, что стоит на том же месте под другой 6.
  3. Первая несовпавшая пара сразу возвращает false наверх, поэтому остальное не сравниваем.

Сложность

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

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

Решить на LeetCode ↗

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