【Название Описание】
Рекурсивное решение, условия для того, чтобы два дерева были зеркальным отражением друг друга, таковы: корневой узел один и тот же, левая ветвь одного дерева такая же, как правая ветвь другого дерева, правая ветвь одного дерева является так же, как левая ветвь другого дерева. Во-первых, введите левый и правый дочерние узлы корневого узла в функцию dfs.Функция функции dfs состоит в том, чтобы судить, симметричны ли два дерева с этими двумя узлами в качестве корневых узлов.
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root:return self.dfs(root.left,root.right)
return True
def dfs(self,root1,root2):
if not root1 and not root2:return True
if not root1 or not root2:return False
return root1.val==root2.val and self.dfs(root1.left,root2.right) and self.dfs(root1.right,root2.left)
[Анализ второй идеи]
С помощью очередей она решается итерационным способом, аналогично BFS, каждый раз, когда узлы каждого слоя помещаются в очередь и выводятся из нее.
def isSymmetric(self, root: TreeNode) -> bool:
if not root: return True
queue=[]
queue.append(root.left)
queue.append(root.right)
while(queue):
root1=queue.pop()
root2=queue.pop()
if not root1 and not root2:
continue
if not root1 or not root2:
return False
if root1.val!=root2.val:
return False
if root1.left or root2.left or root1.right or root2.right:
queue.append(root1.left)
queue.append(root2.right)
queue.append(root1.right)
queue.append(root2.left)
return True
Временная сложность обоих методов составляет O(n), поскольку каждый узел посещается только один раз. В методе 1 сложность пространства связана с высотой дерева и глубиной рекурсивного стека. Метод 2 связан с тем, когда результат может быть возвращен.Если результат получен после посещения всех узлов, то в очередь добавляется n элементов, что равно O(n).