对称二叉树

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

递归

class Solution {
    public boolean isSymmetric(TreeNode root) {
       if(root==null) return true;
       return compare(root.left,root.right);
    }

    public boolean compare(TreeNode left, TreeNode right){
       if(left==null&&right!=null) return false;
       else if(left!=null&&right==null) return false; 
       else if(left==null&&right==null) return true; //叶子结点直接返回
       else if(left.val != right.val) return false;
       //if(left.val == right.val) 如果左右结点相等，返回下一层
       return compare(left.left,right.right)&&compare(left.right,right.left); //左左和右右比较 左右和右左比较
    }
}

迭代（队列实现）

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