動機
複習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