“This is the 22nd day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Topic describes

Given a binary tree, check whether it is mirror – symmetric.

For example, binary trees [1,2,2,3,4,4,3] are symmetric.

    1
   / \
  2   2
 / \ / \
3  4 4  3
Copy the code

But the following [1,2,2,null,3,null,3] is not mirror symmetric:

1 / \ 2 2\3 3Copy the code

Advancements: Can you solve this problem recursively and iteratively?

Their thinking

A recursive symmetric tree is essentially a mirror image of a left subtree and a right subtree, so you can specify two Pointers, L, that move in opposite directions at the same time to traverse the tree. Both Pointers start at the root, then l moves right, R moves left, l moves left, R moves right. Check each time whether the values of the current L and R nodes are equal, and whether the left and right subtrees are symmetric.

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)
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)


Iterating into queues is a common way to recursively –> iterate over transformations.

We enqueue root twice during initialization. Extract two nodes p and q at a time and compare their values for equality (every two consecutive nodes in the queue should be equal), then insert the left and right children of p and Q into the queue in reverse order. The algorithm ends when the queue is empty, or when the continuous nodes P and Q taken from the queue are not equal (the tree is asymmetric).

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 orp.val ! = q.val:return False
        queue.append(p.left)
        queue.append(q.right)
        queue.append(p.right)
        queue.append(q.left)
    return True
Copy the code
  • Time complexity: O(n)
  • Space complexity: O(n)

Clocked today, the current progress is 10/200.

This is what I want to share today. Search Python New Horizons on wechat, bringing you more useful knowledge every day. More organized nearly a thousand sets of resume templates, hundreds of e-books waiting for you to get oh! In addition, there are Python small white communication group, if you are interested in the way to contact me!