root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Input: root = [1,2,2,3,4,4,3] Output: true
Input: root = [1,2,2,null,3,null,3] Output: false
left: nodes of the left parts
right: nodes of the right parts
1) Conditions for Symmetric Tree
- If the both left and right node is
None, its Symmetric.
- If the one of the left and right node is
None, its not Symmetric.
- If the value is different, its not symmetirc. In other words, the value have to be same to be a symmetric tree.
2) How to check the child nodes : BFS Search
- pop the left element(
pop(0)) from the
- For the left node's child, append the
left.left first and then
- For the right node's child, append the
right.right first and then
If you see the above picture, you will understand why.
For the child node(both left and right) popped off from the
left should be put in order of left->right, and the child node(both left and right) popped off form the
right should be put in order of right->left.
class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: ''' left: left part nodes right: right part nodes ''' left=[root.left] right=[root.right] while left and right: l_node=left.pop(0) r_node=right.pop(0) # if the both l_node and r_node is None, its symmetric if not l_node and not r_node: continue # if one of the two is None, its not symmetric if not l_node or not r_node: return False # if the value is different, its not symmetirc if l_node.val!=r_node.val: return False # append the left child and right node left.append(l_node.left) left.append(l_node.right) right.append(r_node.right) right.append(r_node.left) return True
Could you solve it both recursively and iteratively?
class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: return self.recursion(root.left, root.right) def recursion(self, l_node,r_node): if l_node is None and r_node is None: return True if l_node is None or r_node is None: return False if l_node.val==r_node.val: return self.recursion(l_node.left, r_node.right) and self.recursion(l_node.right, r_node.left) else: return False