101. Symmetric Tree

Easy (LinkedIn, Bloomberg, Microsoft)

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:

Bonus points if you could solve it both recursively and iteratively.

/**

• Definition for a binary tree node.
• public class TreeNode {
• int val;
• TreeNode left;
• TreeNode right;
• TreeNode(int x) { val = x; }
• } */

Explaination

recursively and iteratively

Solution 1: recursively

public class Solution {

// test case:
// root == null

public boolean isSymmetric(TreeNode root) {
    if(root == null) {
        return true;
    }

    return isSymmetric(root.left, root.right);
}

public boolean isSymmetric(TreeNode n1, TreeNode n2) {
    if(n1 == null || n2 == null) {
        if(n1 == null && n2 == null) {
            return true;
        } else {
            return false;
        }
    } else if(n1.val != n2.val) {
        return false;
    }

    return isSymmetric(n1.left, n2.right) && isSymmetric(n1.right, n2.left);
}

}

Solution 2: iteratively

public class Solution {

// test case:
// root == null

public boolean isSymmetric(TreeNode root) {
    if(root == null) {
        return true;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root.left);
    queue.offer(root.right);

    while(queue.size() > 1) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();

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

        queue.offer(left.left);
        queue.offer(right.right);
        queue.offer(left.right);
        queue.offer(right.left);
    }

    return true;
}

}