Symmetric Tree
Дано бинарное дерево, хранящееся в массиве tree в порядке уровней. Корень находится по индексу 0, потомки узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце массива могут быть дополнительные элементы -1. Верните true, если дерево является зеркальным отражением самого себя относительно вертикальной линии, проходящей через корень, и false в противном случае. Должны совпадать и форма, и значения.
Функция
- treeinteger-array
- двоичное дерево в порядке уровней, где -1 обозначает пустое место
- Возвращаетboolean
- true, если дерево зеркально симметрично, иначе false
Ограничения
1 ≤ tree.length ≤ 32767- Каждый
tree[i]равен-1или значению, для которого0 ≤ tree[i] ≤ 1000. tree[0]никогда не равно-1, поэтому в дереве есть как минимум один узел.- Массив может заканчиваться дополнительными элементами
-1после последнего узла. - Оба потомка пустого места тоже пусты, а глубина не превышает
14.
Примеры
- Ввод
- tree = [1, 2, 2, 3, 4, 4, 3]
- Вывод
- true
- Пояснение
- Сложите дерево пополам. Две
2с индексами1и2встречаются, внешние3с индексами3и6встречаются, а внутренние4на позициях4и5встречаются.
- Ввод
- tree = [1, 2, 2, -1, 3, -1, 3]
- Вывод
- false
- Пояснение
- Обе
3находятся справа от своих родителей. В зеркальном отражении правый потомок левой2(индекс4) должен быть обращён к левому потомку правой2(индекс5), а индекс5пуст.
- Ввод
- tree = [4, 6, 6, 5, -1, -1, 9]
- Вывод
- false
- Пояснение
- Форма представляет собой зеркальное отражение: индекс
3находится напротив индекса6, и в обоих есть узел. Их значения различаются:5и9, поэтому дерево несимметрично.
Дополнительный вопрос
Если форма дерева симметрична, но некоторые значения отличаются, какое минимальное число значений узлов нужно изменить, чтобы дерево стало симметричным?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Какому узлу должен соответствовать левый потомок корня? А какому узлу должен соответствовать левый потомок этого узла?
Сравнивайте по две позиции за раз. Они являются зеркальными, если обе пусты или если в них хранится одно и то же значение, а дочерние узлы перекрещиваются: левый дочерний узел одного зеркально соответствует правому дочернему узлу другого, а правый дочерний узел одного — левому дочернему узлу другого.
Храни стек пар индексов, начиная с
(1, 2). Извлеки пару: пропусти её, если обе позиции пусты; заверши проверку неудачей, если пуста только одна позиция или значения различаются; в противном случае добавь в стек(2*a+1, 2*b+2)и(2*a+2, 2*b+1).
Решение
Симметрия — это свойство пар. У каждого узла есть парный узел в зеркальной позиции по другую сторону от корня, а парный узел левого потомка — правый потомок. Поэтому узел никогда не сравнивают с его собственными потомками: две половины дерева обходят одновременно в противоположных направлениях, сравнивают структуру и значение в каждой паре и останавливаются на первой паре, в которой обнаруживается различие.
Сравните каждый уровень с его обратным
Идея
Сначала разберёмся, как перемещаться по массиву. Узел с индексом i имеет левого потомка с индексом 2*i+1, а правого — с индексом 2*i+2. Потомок существует, только если его индекс находится в пределах массива и значение по этому индексу не равно -1. В массиве [1, 2, 2, 3, 4, 4, 3] у корня 1 потомки находятся по индексам 1 и 2, а у узла 2 с индексом 1 потомки находятся по индексам 3 и 4.
Теперь рассмотрим дерево уровень за уровнем. Зеркальное изображение читается одинаково слева направо и справа налево, поэтому каждый уровень, записанный вместе с пустыми местами, должен читаться одинаково в обоих направлениях. В первом примере уровни ниже корня выглядят так: 2 2 и 3 4 4 3. Во втором они выглядят так: 2 2, а затем -1 3 -1 3. В обратном порядке это 3 -1 3 -1, поэтому ответ — false.
Пустые места должны оставаться в строке. Без них нижний уровень второго примера выглядел бы как 3 3 и проверка прошла бы. Для каждого места потомка каждого реального узла на уровне запишите по одному элементу, а для пустого места — -1; потомки пустых мест тоже пустые, поэтому они ничего не добавляют. Каждый узел посещается один раз, поэтому временная сложность составляет O(n), а в памяти одновременно хранится один уровень: O(w) для самого широкого уровня шириной w.
Алгоритм
- Начни со списка, содержащего корневой индекс
0. - Для каждого индекса в списке, слева направо, запиши обе позиции потомков: значение потомка, если он существует, или
-1, если позиция пуста. Собери существующих потомков для следующего уровня. - Если эта строка позиций потомков отличается от своей обратной последовательности, верни
false. - Перейди на следующий уровень и повторяй, пока он не опустеет, затем верни
true.
def isSymmetric(tree):
n = len(tree)
level = [0] # the real nodes of one level, left to right
while level:
row = [] # the child spots under this level, -1 for an empty one
next_level = []
for i in level:
for child in (2 * i + 1, 2 * i + 2):
if child < n and tree[child] != -1:
row.append(tree[child])
next_level.append(child)
else:
row.append(-1)
if row != row[::-1]:
return False
level = next_level
return TrueРекурсия на зеркальных парах
Идея
Вместо целых уровней сравнивайте два поддерева: левое поддерево корня, которое начинается с индекса 1, и его правое поддерево, которое начинается с индекса 2. Два узла зеркальны друг другу, если оба пусты или если в обоих хранится одно и то же значение, а их потомки расположены крест-накрест. Левый потомок одного зеркален правому потомку другого (внешняя пара), а правый потомок одного зеркален левому потомку другого (внутренняя пара).
В первом примере mirrors(1, 2) сравнивает две 2, затем вызывает mirrors(3, 6) для внешней пары 3 и mirrors(4, 5) для внутренней пары 4. В каждом из этих случаев ниже находятся только пустые узлы, поэтому вызовы возвращают true. Во втором примере mirrors(4, 5) обнаруживает 3 по индексу 4 напротив пустого узла по индексу 5, возвращает false, и это значение false передаётся вверх до самого корня.
Каждый реальный узел входит не более чем в одну пару, поэтому время выполнения составляет O(n). Глубина стека вызовов равна глубине дерева, то есть O(h), и в данном случае составляет не более 14 кадров.
Алгоритм
- Напишите
mirrors(a, b). Место пусто, если его индекс выходит за конец или в нём хранится-1. Если оба места пусты, вернитеtrue; если пусто только одно, вернитеfalse. - Если
tree[a]иtree[b]различаются, вернитеfalse. - В противном случае верните
mirrors(2*a+1, 2*b+2)иmirrors(2*a+2, 2*b+1). - Верните
mirrors(1, 2). У корня без дочерних узлов получаются два пустых места, а этоtrue.
def isSymmetric(tree):
n = len(tree)
def mirrors(a, b):
# Spots a and b must hold the same value, or both be empty.
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a or empty_b:
return empty_a and empty_b
return (tree[a] == tree[b]
and mirrors(2 * a + 1, 2 * b + 2) # outer pair
and mirrors(2 * a + 2, 2 * b + 1)) # inner pair
return mirrors(1, 2)Явный стек зеркальных пар
Идея
Рекурсии нужна только одна вещь: пары, которые ещё нужно проверить. Храни эти пары в собственном стеке — и вызовы исчезнут. Начни с пары (1, 2). Извлеки пару. Если обе позиции пусты, под ними ничего нет, поэтому переходи дальше. Если одна позиция пуста или значения различаются, дерево несимметрично. В противном случае добавь в стек внешнюю пару (2*a+1, 2*b+2) и внутреннюю пару (2*a+2, 2*b+1).
Порядок проверки пар не имеет значения, потому что дерево симметрично, только если совпадают все пары. Стек задаёт обход в глубину; очередь обеспечила бы обход по уровням и работала бы так же. Третий пример останавливается на первой неподходящей паре — (3, 6), в которой находятся значения 5 и 9.
Каждое извлечение обрабатывает одну пару, а каждый реальный узел входит не более чем в одну пару, поэтому временная сложность составляет O(n). В стеке хранится примерно одна ожидающая пара на каждый уровень текущего пути — O(h) памяти, и беспокоиться об ограничении рекурсии не нужно.
Алгоритм
- Поместите пару
(1, 2)в стек. - Извлеките пару
(a, b). Если обе позиции пусты (индекс за пределами массива или-1), перейдите к следующей паре. - Если пустая только одна позиция или
tree[a]отличается отtree[b], вернитеfalse. - Поместите в стек
(2*a+1, 2*b+2)и(2*a+2, 2*b+1). - Когда стек опустеет, верните
true.
def isSymmetric(tree):
n = len(tree)
stack = [(1, 2)] # pairs of spots that must mirror each other
while stack:
a, b = stack.pop()
empty_a = a >= n or tree[a] == -1
empty_b = b >= n or tree[b] == -1
if empty_a and empty_b:
continue
if empty_a or empty_b or tree[a] != tree[b]:
return False
stack.append((2 * a + 1, 2 * b + 2)) # outer pair
stack.append((2 * a + 2, 2 * b + 1)) # inner pair
return True
Ловушки и крайние случаи
В большинстве неправильных ответов сравнивают не ту пару узлов или забывают, что пустое место тоже является частью структуры.
- Проверка каждого поддерева отдельно. Левое поддерево не обязано быть симметричным само по себе: в
[1, 2, 2, 3, 4, 4, 3]поддерево2, 3, 4несимметрично, а всё дерево — симметрично. Оно должно зеркально отражать правое поддерево. - Неправильное сопоставление потомков. Левый потомок с одной стороны сопоставляется с правым потомком с другой:
(2*a+1, 2*b+2)и(2*a+2, 2*b+1), но никогда не(2*a+1, 2*b+1). - Сравнение только значений. Если убрать пустые места из
[1, 2, 2, -1, 3, -1, 3], на каждом уровне значения будут одинаковыми при чтении в обоих направлениях, но дерево не будет симметричным. Сохраняйте-1в строке уровня или проверяйте пустоту при сравнении пары. - Выход за пределы массива. Индекс за пределами массива соответствует пустому месту. Перед чтением
tree[a]проверьтеa < n; у дерева с одним узлом индексов1и2вообще нет. - Остановка после первой совпавшей пары. Одна подходящая пара ничего не доказывает; возвращайте
trueтолько после проверки всех пар. - Путаница со смещением в Lua и R, где массивы начинаются с 1. Используйте для индексов узлов отсчёт с 0 в выражении
2*i+1, а считывайте значения поtree[i + 1].
Частые вопросы3
Какова временная сложность алгоритма для симметричного дерева?
Каждый реальный узел сравнивается один раз в составе одной зеркальной пары, поэтому временная сложность составляет O(n). Рекурсивная версия и версия со стеком используют дополнительную память O(h) для ожидающих пар на текущем пути. Версия с обработкой уровней хранит в памяти один уровень — O(w) для самого широкого уровня.
Как проверить, является ли бинарное дерево симметричным, без рекурсии?
Храните стек или очередь пар узлов, которые должны быть зеркальным отражением друг друга, начиная с двух дочерних узлов корня. Извлеките пару, завершите проверку при несовпадении и добавьте внешнюю пару и внутреннюю пару их дочерних узлов. Если стек опустеет без несовпадений, дерево симметрично.
В чём разница между симметричным деревом и двумя одинаковыми деревьями?
Два дерева идентичны, если сравнивать левый узел с левым, а правый — с правым. Дерево симметрично, если его левое поддерево идентично зеркальному отражению правого поддерева, поэтому сравнение выполняется крест-накрест: левый узел с правым, а правый — с левым. Один и тот же код для проверки пар решает обе задачи, если поменять местами пары дочерних узлов.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def isSymmetric(tree):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
tree = [1, 2, 2, 3, 4, 4, 3]
Ожидаемый вывод
true