動機

複習bfs

Problem

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

Input: root = [1,2,2,3,4,4,3]Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]Output: false

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

 

Follow up: Could you solve it both recursively and iteratively?

Sol

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def sym(rs):
            if not rs:
                return False
            else:
                rs = [x.val if x else None for x in rs]
                return rs == list(reversed(rs))
        q = deque([[root]])
        while q:
            rs = q.popleft()
            #print([x.val if x else None for x in rs])
            if sym(rs):
                ret = []
                for r in rs:
                    ret += [r.left,r.right] if r else []
                if ret: # IMPORTANT!!!
                    q.append(ret)
            else:
                return False
        return True