题目描述 给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [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函数就能够判定整棵树是否是对称的。 解法2 解法2采用另一个比较直观的思路，比较容易理解。我们观察图1，如果树是对称的，那么我们横向读取每一层的节点，都会发现他们是“回文序列”，也就是从左到右读和从右到左读都是一样的。如果有任何一层读起来不是回文序列，那么这棵树就不是对称的！ 为了实现按层次遍历，我们使用BFS算法，用一个队列来实现。但是队列没法随机访问，我们在实现时使用数组来模拟队列。如果使用数组的remove方法来出队，会涉及到元素移动，使得时间复杂度达到O(n^2)。因此，我们采用“双缓冲”方法，创建变量queue以及buffer，从queue中读取当前层到节点并访问，将下一层节点放入buffer，然后交换queue与buffer。如果你不清楚二叉树层次变量，可以参考这个。 时间复杂度为O(n)，空间复杂度为O(n)。全部代码如下：