1 /**
  2      * Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
  3      * @param root
  4      * @return
  5      */
  6     public boolean isSymmetricRecursively(TreeNode root){
  7         if(root == null)
  8             return true;
  9         return isSymmetricR(root.left, root.right);
 10     }
 11     /**
 12      * 采用迭代的方式，输入的是两个对称位置的节点，如果以这两个节点为root的子树是对称的，则
 13      * 左边的左子树和右边的右子树相同，且左边的右子树和右边的左子树相同，且这两个子树的树根的值相等
 14      * @param left
 15      * @param right
 16      * @return
 17      */
 18     private boolean isSymmetricR(TreeNode left, TreeNode right){
 19         if(left== null && right == null)
 20             return true;
 21         if(left == null && right!=null || right == null && left!=null)
 22             return false;
 23         if(left.left == null && left.right == null &&
 24                 right.left == null && right.right == null)
 25             return left.val == right.val;
 26         boolean f1 = (left.val == right.val);
 27         boolean l1 = isSymmetricR(left.left, right.right);
 28         boolean r1 = isSymmetricR(left.right, right.left);
 29         return f1&&l1&&r1;
 30         
 31     }
 32     /**
 33      * Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
 34      * solve it iteratively
 35      * @param root
 36      * @return
 37      */
 38     public boolean isSymmetricIteratively(TreeNode root){
 39         if(root == null || (root.left == null && root.right == null))
 40             return true;
 41         LinkedList<TreeNode> qleft = new LinkedList<TreeNode>();
 42         LinkedList<TreeNode> qright = new LinkedList<TreeNode>();
 43         
 44         if(root.left!=null && root.right == null ||
 45                 root.right!=null && root.left == null)
 46             return false;
 47         qleft.offer(root.left);
 48         qright.offer(root.right);
 49         
 50         while(!qleft.isEmpty() && !qright.isEmpty()){
 51             TreeNode left = qleft.poll();
 52             TreeNode right = qright.poll();
 53             
 54             if(left.val != right.val)
 55                 return false;
 56             
 57             if(left.right != null && right.left!=null){
 58                 qleft.offer(left.right);
 59                 qright.offer(right.left);
 60             }else if(left.right!= null && right.left == null ||
 61                     left.right == null && right.left !=null)
 62                 return false;
 63             
 64             if(right.right != null && left.left!=null){
 65                 qleft.offer(left.left);
 66                 qright.offer(right.right);
 67             }else if(right.right!= null && left.left == null ||
 68                     right.right == null && left.left !=null)
 69                 return false;
 70         }
 71         return true;
 72     }
 73     /**
 74      * by BFS, to check if they are equal or not
 75      * Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
 76      * @param p
 77      * @param q
 78      * @return
 79      */
 80     public boolean isSameTree(TreeNode p, TreeNode q){
 81         if(p == null && q == null)
 82             return true;
 83         if(p == null && q!=null || p!=null && q==null)
 84             return false;
 85         LinkedList<TreeNode> pqueue = new LinkedList<TreeNode>();
 86         LinkedList<TreeNode> qqueue = new LinkedList<TreeNode>();
 87         
 88         pqueue.offer(p);
 89         qqueue.offer(q);
 90         
 91         while(!pqueue.isEmpty() && !qqueue.isEmpty()){
 92             TreeNode pC = pqueue.poll();
 93             TreeNode qC = qqueue.poll();
 94             //have same value
 95             if(pC.val!=qC.val)
 96                 return false;
 97             //structurally identical or not
 98             if(pC.left!=null && qC.left == null ||
 99                     pC.left == null && qC.left!=null)
100                 return false;
101             else if(pC.left!=null && qC.left!=null){
102                 pqueue.offer(pC.left);
103                 qqueue.offer(qC.left);
104             }
105             
106             if(pC.right == null && qC.right != null || 
107                     pC.right!=null && qC.right == null)
108                 return false;
109             else if(pC.right!=null && qC.right!=null){
110                 pqueue.offer(pC.right);
111                 qqueue.offer(qC.right);
112             }
113         }
114         /**
115          * there is no need
116          * if(pqueue.isEmpty() && !qqueue.isEmpty() ||
117                 qqueue.isEmpty() && !pqueue.isEmpty())
118             return false;
119         */
120         return true;
121     }