每日一道算法题--leetcode 101--对称二叉树--python

【题目描述】

递归解决,两棵树互为镜像的条件是：根节点一样，一棵树的左分支与另一棵树的右分支相同；一棵树的右分支和另一棵树的左分支相同。首先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)。