101. Symmetric Tree Leetcode Java

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.

Solution:

1. Recursively

In order to determine if a tree is symmetric, we have to check if its left child is a mirror of its right child, furthermore, we have to check if left.val==right.val && left.right is mirror of right.left && right.left is mirror of left.right. So we can recursively check if the tree satisfy these requirements. 

 public boolean isSymmetric(TreeNode root) {  
    if(root==null) return true;  
    return helper(root.left,root.right);  
   }  
   public boolean helper(TreeNode l, TreeNode r){  
     if(l==null) return r==null;  
     if(r==null) return l==null;  
     return l.val==r.val && helper(l.left, r.right) && helper(l.right,r.left);  
   }  

2. Iteratively
Use the technique of level order traversal, for left child add its children from left to right, for right child add its children from right to left, then compare nodes one by one with two queues.

 public boolean isSymmetric(TreeNode root) {  
   if(root==null) return true;  
   LinkedList<TreeNode> q1=new LinkedList<TreeNode>();  
   LinkedList<TreeNode> q2=new LinkedList<TreeNode>();  
   q1.offer(root.left);  
   q2.offer(root.right);  
   while(!q1.isEmpty() && !q2.isEmpty()){  
     TreeNode l=q1.poll();  
     TreeNode r=q2.poll();  
     if(l==null && r!=null) return false;  
     if(l!=null && r==null) return false;  
     if(l==null && r==null) continue;  
     if(l.val!=r.val) return false;  
     q1.offer(l.left);  
     q1.offer(l.right);  
     q2.offer(r.right);  
     q2.offer(r.left);  
   }  
   return q1.isEmpty() && q2.isEmpty();  
   }