[LeetCode] 101. Symmetric Binary Tree

❓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

[Solution]

We can solve this problem using 2 ways. First, using recursive function. Second, using iterative loop.

Key point is checking left value of left node to right value of right node and right value of left node to left value of right node.

I’ve felt that I’m so weak at binary tree problems… hope to be get better.

Here is full codes of the solution.

1. Recursive

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def recursion(left, right):
            if not left and not right:
                return True
            if not left or not right:
                return False
            
            return left.val == right.val and recursion(left.left, right.right) and recursion(left.right, right.left)
            
        return recursion(root, root)

2. Iterative

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        q = [root, root]
        while q:
            left = q.pop(0)
            right = q.pop(0)

            if not left and not right:
                continue
            if not left or not right:
                return False
            
            if left.val == right.val:
                q.extend([left.left, right.right, left.right, right.left])

            else:
                return False
            
        return True