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   2 / \ / \3  4 4  3

 

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

1   / \  2   2   \   \   3    3

 

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; } * } */class Pair{    TreeNode x;    TreeNode y;    public Pair(TreeNode x, TreeNode y){        this.x = x;        this.y = y;    }}public class Solution {    // recursive    // public boolean isSymmetric(TreeNode root) {    //     if(root == null)    //         return true;            //     return Symmetric(root.left, root.right);    // }    // public boolean Symmetric(TreeNode left, TreeNode right){    //     if(left == null || right == null){    //         return left == right;    //     }    //     if(left.val != right.val){    //         return false;    //     }    //     return Symmetric(left.left, right.right) &&  Symmetric(left.right, right.left);    // }        public boolean isSymmetric(TreeNode root) {        if(root == null || root.left == null && root.right == null)            return true;        Queue
     
       queue = new LinkedList
      
       ();        queue.offer(new Pair(root.left, root.right));        while(!queue.isEmpty()){            Pair values= queue.poll();            if(values.x == null && values.y == null)                continue;            if(values.x == null || values.y == null || values.x.val != values.y.val)               return false;                           if(values.x != null && values.y != null){                queue.offer(new Pair(values.x.left, values.y.right));                queue.offer(new Pair(values.x.right, values.y.left));            }        }        return true;    }}