【题目描述】
【思路一解析】递归解决,两棵树互为镜像的条件是:根节点一样,一棵树的左分支与另一棵树的右分支相同;一棵树的右分支和另一棵树的左分支相同。首先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),因为都只访问了每个节点一次。空间复杂度在方法一中与树的高有关,涉及到递归栈的深度。方法2则与何时才能返回结果有关,如果访问所有节点之后才有结果,那么队列中加入n个元素,为O(n)。