1. 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
2. Solution
I solved this problem like this.
- Step
- I solved this problem using bfs.
- Confirm list value is isSymmetric.
from collections import deque
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
deq = deque([root])
while deq:
round_nodes = list(deq)
deq = deque()
for i in range(len(round_nodes)//2):
if round_nodes[i] == None and round_nodes[-(i+1)] == None:
continue
if round_nodes[i] == None or round_nodes[-(i+1)] == None:
return False
if round_nodes[i].val != round_nodes[-(i+1)].val:
return False
for node in round_nodes:
if node == None:
deq.append(None)
deq.append(None)
continue
deq.append(node.left)
deq.append(node.right)
if deq.count(None) == len(deq):
break
return True
Other solution is more better. That user solved this problem using dfs.
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root.left is None and root.right is None:
return True
def sym(l,r):
if l is None and r is None:
return True
if l is None or r is None:
return False
return l.val == r.val and sym(l.left,r.right) and sym(l.right,r.left)
return sym(root,root)