«Это 22-й день моего участия в ноябрьском испытании обновлений, ознакомьтесь с подробностями события:Вызов последнего обновления 2021 г.".
Описание темы
Имея бинарное дерево, проверьте, является ли оно зеркально симметричным.
Например, бинарное дерево[1,2,2,3,4,4,3]является симметричным.
1
/ \
2 2
/ \ / \
3 4 4 3
Но следующее[1,2,2,null,3,null,3]не является зеркально-симметричным:
1
/ \
2 2
\ \
3 3
Расширенный: вы можете использовать递归и迭代Есть ли два пути решения этой проблемы?
Идеи решения проблем
рекурсия
Симметричное дерево на самом деле является зеркальным отображением левого и правого поддеревьев, поэтому вы можете указать два указателя.l, rВ то же время двигайтесь в противоположном направлении для обхода дерева, оба указателя начинают указывать на корневой узел, затем l 右移时，r 左移，l 左移时，r 右移. Каждый раз, когда вы проверяете текущийlиrРавны ли значения узлов и симметричны ли левое и правое поддеревья.
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def search(l, r):
if not l and not r:
return True
if not l or not r:
return False
return l.val == r.val and search(l.left, r.right) and search(l.right, r.left)
return search(root, root)
- Временная сложность: O(n)
- Космическая сложность: O(n)
повторять
Введение очереди — распространенный метод рекурсивных --> итеративных преобразований.
При инициализации ставим корневой узелrootЗачислен дважды.
Извлечение двух узлов за разp, qи сравните, равны ли их значения (каждые два последовательных узла в очереди должны быть равны), затем поставьтеp, qЛевый и правый дочерние узлы узла нажаты相反вставляются в очередь по порядку. Когда очередь пуста или из очереди взят непрерывный узелp, qКогда они не равны (дерево несимметрично), алгоритм завершается.
def isSymmetric(root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return False
queue = [root, root]
while queue:
p = queue.pop()
q = queue.pop()
if not p and not q:
continue
if not p or not q or p.val != q.val:
return False
queue.append(p.left)
queue.append(q.right)
queue.append(p.right)
queue.append(q.left)
return True
- Временная сложность: O(n)
- Космическая сложность: O(n)
Сегодняшняя регистрация завершена, текущий прогресс — 10/200.
Это то, чем я хочу поделиться сегодня, поиск WeChatНовые горизонты Python, приносить вам больше полезных знаний каждый день.Организовано более тысячи наборов шаблонов резюме, и сотни электронных книг ждут, когда вы их соберете! Существует также группа обмена Python Xiaobai.Если вы заинтересованы, вы можете связаться со мной указанным выше способом!