[LeetCode] Problem 101 - Symmetric Tree

Posted on | In ,

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:

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

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

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

Note

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

Recursive

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean isSymmetric(TreeNode root) {
    if (root == null)
        return true;
    
    return isSymmetricHelper(root.left, root.right);
}

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

Iterative

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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.isEmpty()) {
        TreeNode n1 = queue.poll();
        TreeNode n2 = queue.poll();

        if (n1 == null && n2 == null)
            continue;
        else if (n1 == null || n2 == null || n1.val != n2.val)
            return false;
        
        queue.offer(n1.left);
        queue.offer(n2.right);
        queue.offer(n1.right);
        queue.offer(n2.left);
    }

    return true;
}