Question

link

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

For example, this binary tree is symmetric: 

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

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

Stats

Frequency 2
Difficulty 1
Adjusted Difficulty 2
Time to use 2 ways to solve

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an easy one.

Solution

I solved it using recursion.

The non-recursion solution is using 2 stacks (or queues). I did not write it, but the code is posted as well, copied from this post.

Code

First, recursion

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return check(root.left, root.right);
}

private boolean check(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    if (left.val != right.val) return false;
    return check(left.left, right.right) & check(left.right, right.left);
}

Second, non-recursion

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    Stack<TreeNode> s1 = new Stack<TreeNode>();
    Stack<TreeNode> s2 = new Stack<TreeNode>();
    s1.push(root.left);
    s2.push(root.right);
    while (!s1.empty() && !s2.empty()) {
        TreeNode n1 = s1.pop();
        TreeNode n2 = s2.pop();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null) return false;
        if (n1.val != n2.val) return false;
        s1.push(n1.left);
        s2.push(n2.right);
        s1.push(n1.right);
        s2.push(n2.left);
    }
    return true;
}