class Solution {
    
    // 返回以t1，t2分别为根节点的二叉树 是否对称
    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) { // 叶子结点的左右两个NULL 也要看  递归到了这一步说明对称
            return true;
        }
        // 1. t1空 t2 不空 false   2. t1不空 t2空 false   3. t1和t2的数据域不相等 false
        if (t1 == null || t2 == null || t1.val != t2.val) {
            return false;
        }
        return isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left); // t1的左子树与t2的右子树 t1的右子树与t2的左子树是否对称 
    }
    
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isMirror(root.left, root.right);   // 返回根节点左右子树是否对称
    }
}

class Solution {
    
    public boolean BFS(TreeNode t1, TreeNode t2) {
        Queue<TreeNode> q1 = new LinkedList<>();   // 装t1
        Queue<TreeNode> q2 = new LinkedList<>();   // 装t2
        q1.offer(t1);
        q2.offer(t2);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode f1 = q1.poll();
            TreeNode f2 = q2.poll();
            if (f1 == null && f2 == null) { // NULL 结点也入队
                continue; 
            }
             // 1. f1空 f2 不空 false   2. f1不空 f2空 false   3. f1和f2的数据域不相等 false
            if (f1 == null || f2 == null || f1.val != f2.val) {
                return false;
            }
            q1.offer(f1.left);  // t1的入队顺序 是左 右  t2的入队顺序是 右 左  只要两者是反着的就行 
            q1.offer(f1.right);
            q2.offer(f2.right);
            q2.offer(f2.left);
        }
        if (!q1.isEmpty() || !q2.isEmpty()) { // 说明一棵树遍历完了 另外一棵树还没有 肯定不对称
            return false;
        }
        return true;
    }
    
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return BFS(root.left, root.right);  // 返回根节点左 右 子树是否对称
    }
}