Leetcode 101– Symmetric binary trees — Python

【 topic description 】

Recursively, two trees are mirror images of each other if the root node is the same and the left branch of one tree is the same as the right branch of the other tree; The right branch of one tree is the same as the left branch of another tree. First, input the left and right child nodes of the root node into the DFS function. The function of THE DFS function is to judge whether the two trees with these two nodes as the root nodes are symmetric.

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)
Copy the code

【思路二解析】

With the help of queues, solve the problem in an iterative manner, similar to BFS, each time the nodes of each layer are put in and out of queues.

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
            ifroot1.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
Copy the code

The time complexity of both methods is O(n) because each node is accessed only once. Spatial complexity in method one is related to the height of the tree and the depth of the recursive stack. Method 2 depends on when the result is returned. If the result is not returned until all nodes are accessed, then n elements are added to the queue, O(n).