Introduction

In this blog post, we will explore how to solve the LeetCode problem "101" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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?

Explanation

Here's a breakdown of the solution, followed by the Python code:

• Core Idea: The fundamental concept is to compare the left and right subtrees. For the tree to be symmetric, the left subtree must be a mirror image of the right subtree.
• Recursive Comparison: We can achieve this comparison elegantly through recursion. A helper function compares the values of corresponding nodes in the left and right subtrees and recursively checks their children.

• Iterative Comparison (using a queue): We can also iteratively achieve this comparison by using a queue to maintain the nodes for comparison. We check the value of each node and then add the children of the left subtree in the order left.left, left.right and the children of the right subtree in the order right.right, right.left into the queue.

• Complexity: O(N) time, O(N) space, where N is the number of nodes in the tree.

Code

    class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSymmetric(root):
    """
    Determines if a binary tree is symmetric.

    Args:
        root: The root of the binary tree.

    Returns:
        True if the tree is symmetric, False otherwise.
    """

    def isMirror(node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2:
            return False
        return (node1.val == node2.val) and isMirror(node1.left, node2.right) and isMirror(node1.right, node2.left)

    return isMirror(root, root)


def isSymmetricIterative(root):
    """
    Determines if a binary tree is symmetric using an iterative approach.

    Args:
        root: The root of the binary tree.

    Returns:
        True if the tree is symmetric, False otherwise.
    """
    if not root:
        return True

    queue = [root, root]
    while queue:
        node1 = queue.pop(0)
        node2 = queue.pop(0)

        if not node1 and not node2:
            continue
        if not node1 or not node2:
            return False
        if node1.val != node2.val:
            return False

        queue.append(node1.left)
        queue.append(node2.right)
        queue.append(node1.right)
        queue.append(node2.left)

    return True