Symmetric Tree

Share

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:

Contents

Solution 1: Recursive

A tree is symmetric if its left subtree is a mirror of its right subtree. Two trees are mirrors if:

Java
public boolean isSymmetric(TreeNode root) {
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    return left.val == right.val
        && isMirror(left.left,  right.right)  // outer pair
        && isMirror(left.right, right.left);  // inner pair
}

Solution 2: Iterative (Queue)

Enqueue pairs of nodes that should be mirrors. At each step, dequeue a pair and check:

Java
public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root.left);
    queue.offer(root.right);

    while (!queue.isEmpty()) {
        TreeNode left  = queue.poll();
        TreeNode right = queue.poll();

        if (left == null && right == null) continue;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;

        // Enqueue outer pair and inner pair
        queue.offer(left.left);  queue.offer(right.right);
        queue.offer(left.right); queue.offer(right.left);
    }
    return true;
}

Complexity Analysis