LeetCode 101.对称二叉树 BFS

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

这道题有两种方法来解决
一种方法是用递归,一种方法是迭代。

1.递归法:

两棵树互为镜像的条件:
(1).这两个树的根节点值相同
(2).每棵树的左子树都与另一棵树的右子树对称

AC代码：

public  boolean isSymmetric(TreeNode root) {

       return ismirror(root,root);

   }



public  boolean ismirror(TreeNode p,TreeNode q){
       if (p==null && q==null) return true;

       if (p==null || q==null){
           return false;
       }

       if (p.val==q.val){
           return ismirror(p.left,q.right)&&ismirror(p.right,q.left);
       }

       return false;

   }

2.迭代方法

 //利用迭代的方法
  public boolean isSymmetric2(TreeNode root){
      Queue<TreeNode> queue = new LinkedList<>();
      queue.add(root);
      queue.add(root);

       while (!queue.isEmpty()){
           TreeNode p  = queue.poll();
           TreeNode q = queue.poll();
           if (p==null && q==null) continue;

           if (p==null || q==null) return false;


           if (p.val !=q.val) return  false;

           queue.add(p.left);
           queue.add(q.right);
           queue.add(p.right);
           queue.add(q.left);


       }

       return true;
  }

这里要注意进队的顺序。