题目描述

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

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

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

https://leetcode-cn.com/problems/symmetric-tree/

解法1

为了解决问题，我们先画一个比较general的case来帮助我们思考。我们构建一个4层的对称二叉树，如图1所示。我们可以发现，如果一颗树是对称二叉树，那么它的左子树与右子树是互为镜像的。如图1所示，跟节点root的左子树root.left与右子树root.right互为镜像。因此，我们可以把问题转化为判断两个二叉树是否互为镜像。

为了判断两颗二叉树是否互为镜像，我们创建函数private boolean isMirror(TreeNode node1, TreeNode node2)，用来判定两颗二叉树node1与node2是否互为镜像。那我们如何实现这个函数呢？

• 首先，如果node1与node2都是空，很好理解，他们是镜像的。
• 如果node1与node2有一个为空，另一个非空，那么肯定不是镜像的。
• 如果node1与node2都非空，但是node对应的值不想相等，那么也不互为镜像。
• 如果node1与node2非空，且值相等，那我们还需要递归的判断node1的右子树与node2的左子树互为镜像，且node1的左子树与node2的右子树互为镜像。

我们按照上面的规则递归的判定，直到我们都访问到叶节点后返回我们才能确定两棵树是互为镜像的。如果在递归的过程中发现有不符合上述规则都情况，那么这两棵树就不是镜像的。

下面的代码采用DFS方式判定，我们按照上面4条规则实现了isMirror函数，然后我们把root的左子树与右子树传递给isMirror函数就能够判定整棵树是否是对称的。

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

    private boolean isMirror(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null)
            return true;
        else if (node1 == null || node2 == null)
            return false;

        return node1.val == node2.val &&
                isMirror(node1.left, node2.right) &&
                isMirror(node1.right, node2.left);
    }
}

解法2

解法2采用另一个比较直观的思路，比较容易理解。我们观察图1，如果树是对称的，那么我们横向读取每一层的节点，都会发现他们是“回文序列”，也就是从左到右读和从右到左读都是一样的。如果有任何一层读起来不是回文序列，那么这棵树就不是对称的！

为了实现按层次遍历，我们使用BFS算法，用一个队列来实现。但是队列没法随机访问，我们在实现时使用数组来模拟队列。如果使用数组的remove方法来出队，会涉及到元素移动，使得时间复杂度达到O(n^2)。因此，我们采用“双缓冲”方法，创建变量queue以及buffer，从queue中读取当前层到节点并访问，将下一层节点放入buffer，然后交换queue与buffer。如果你不清楚二叉树层次变量，可以参考这个。

时间复杂度为O(n)，空间复杂度为O(n)。全部代码如下：

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> queue = new ArrayList<>();
        List<TreeNode> buffer = new ArrayList<>();

        if (root == null)
            return true;

        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();

            // 判断当前是否是回文序列
            for (int i = 0; i < size / 2; i++) {
                TreeNode front = queue.get(i);
                TreeNode end = queue.get(size - i - 1);

                if (front != null && end != null) {
                    if (front.val != end.val)
                        return false;
                } else if (front != null || end != null)
                    return false;
            }

            for (TreeNode node : queue) {
                if (node != null) {
                    buffer.add(node.left);
                    buffer.add(node.right);
                }
            }

            queue.clear();
            List<TreeNode> tmp = queue;
            queue = buffer;
            buffer = tmp;
        }

        return true;
    }
}