101.对称二叉树

题目：

思路1.迭代：

迭代：
构造一个队列，其中每对相邻的两个节点值相同的话，则镜像对称
在往其中添加节点时，两个节点的左右子节点按相反的顺序插入队列中

代码1.迭代：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 //迭代
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<TreeNode>();//构造一个队列，每一对相邻的两个节点相同时，二叉树镜像对称
        if(root == null)
            return true;
        //两次加入根节点，方便后面代码统一格式
        deque.offer(root);
        deque.offer(root);

        while(!deque.isEmpty()){
            TreeNode a = deque.poll();
            TreeNode b = deque.poll();
            if(a == null && b == null)
                continue;
            if((a == null || b == null) || a.val != b.val)
                return false;

            //添加节点，为了下一次判断是否对称
            deque.offer(a.left);
            deque.offer(b.right);

            deque.offer(a.right);
            deque.offer(b.left);
        }
        return true;
    }
}

复杂度分析：

时间复杂度：O（n）
空间复杂度：O（n）

代码2.递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        return check(root.left,root.right);//这么写比写成return check(root,root)少比较一遍
    }
    public boolean check(TreeNode a,TreeNode b){
        if(a == null && b == null)
            return true;
        if((a == null || b == null) || (a.val != b.val))
            return false;
        return check(a.left,b.right)&&check(a.right,b.left) ;
    }
}

复杂度分析：

时间复杂度：O（n）
空间复杂度：O（n）