LeetCode101 对称二叉树

题目

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

 例如，二叉树 [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
   
 进阶： 
 你可以运用递归和迭代两种方法解决这个问题吗？ 

方法

递归

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
    private boolean check(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null){
            return true;
        }
        if(root1==null||root2==null){
            return false;
        }
        return (root1.val==root2.val)&&check(root1.left,root2.right)&&check(root1.right,root2.left);
    }
}

迭代

• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null ){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root.left);
        queue.add(root.right);
        while(!queue.isEmpty()){
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if(t1 == null && t2 == null){
                continue;
            }else if(t1 == null || t2 == null){
                return false;
            }else if(t1.val != t2.val){
                return false;
            }
            queue.add(t1.left);
            queue.add(t2.right);
            queue.add(t1.right);
            queue.add(t2.left);
        }
        return true;
    }
}

LeetCode101 对称二叉树

原文：https://www.cnblogs.com/ermiao-zy/p/14864229.html