[Leetcode] Symmetric Tree

Problem

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.

Algorithm

Recursive

A tree is symmetric, 

• if it is null, 
• else if it has not children
• else if root.left.val = root.right.val,  and both subtrees are symmetric

Iterative

If each level of the tree are symmetric, the tree is symmetric. 

Using the iterative level order traversal of tree algorithm, we can check if the tree is symmetric in each level. The curLevel  stores the nodes from left to right, as usual. While the curLevelRev stores the nodes from right to left, in reversed order. Each time, we remove the first node n of curLevel and the first node r of curLevelRev, where n and r form a pair of mirrored nodes.

• If they have different value, return false. 
• Else if they have asymmetric structure, return false
• Else, add n.left to curLevel, r.right to curLevelRev, if not null, add n.right to curLevel, r.left to curLevelRev, if not null. 

Code