判断二叉树是否是镜像对称

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

 例如，二叉树 [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,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

思路：用高度大于2的二叉树举例来说吧，也就是上面第一个例子，只要结点1的左孩子和结点2的右孩子相等，并且结点1的右孩子和结点2的左孩子相等，我们就认为是镜像，前提是结点1和结点2兄弟结点；

递归实现如下：

public static boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return in(root.left,root.right);
    }


    //递归
    public static boolean in(TreeNode l1,TreeNode l2){
        if(l1 == null && l2 == null) return true;
        if(l1 == null || l2 == null) return false;
        return l1.val == l2.val && in(l1.left,l2.right) && in(l1.right,l2.left);
    }

public static boolean isSymmetric(TreeNode root) { if(root == null) return true; return in(root.left,root.right); } //递归 public static boolean in(TreeNode l1,TreeNode l2){ if(l1 == null && l2 == null) return true; if(l1 == null || l2 == null) return false; return l1.val == l2.val && in(l1.left,l2.right) && in(l1.right,l2.left); }

非递归如下：

//迭代
    public static boolean isSymm(TreeNode root){
        if(root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            q.add(t1.left);
            q.add(t2.right);
            q.add(t1.right);
            q.add(t2.left);
        }
        return true;
    }

//迭代 public static boolean isSymm(TreeNode root){ if(root == null) return true; Queue q = new LinkedList<>(); q.add(root); q.add(root); while (!q.isEmpty()) { TreeNode t1 = q.poll(); TreeNode t2 = q.poll(); if (t1 == null && t2 == null) continue; if (t1 == null || t2 == null) return false; if (t1.val != t2.val) return false; q.add(t1.left); q.add(t2.right); q.add(t1.right); q.add(t2.left); } return true; }

给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [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 思路：用高度大于2的二叉树举例来说吧，也就是上面第一个例子，只要结点1的左孩子和结点2的右孩子相等，并且结点1的右孩子和结点2的左孩子相等，我们就认为是镜像，前提是结点1和结点2兄弟结点； 递归实现如下： public static boolean isSymmetric(TreeNode root) { if(root == null) return true; return in(root.left,root.right); } //递归 public static boolean in(TreeNode l1,TreeNode l2){ if(l1 == null && l2 == null) return true; if(l1 == null || l2 == null) return false; return l1.val == l2.val && in(l1.left,l2.right) && in(l1.right,l2.left); } 非递归如下： //迭代 public static boolean isSymm(TreeNode root){ if(root == null) return true; Queue q = new LinkedList<>(); q.add(root); q.add(root); while (!q.isEmpty()) { TreeNode t1 = q.poll(); TreeNode t2 = q.poll(); if (t1 == null && t2 == null) continue; if (t1 == null || t2 == null) return false; if (t1.val != t2.val) return false; q.add(t1.left); q.add(t2.right); q.add(t1.right); q.add(t2.left); } return true; }