当前位置 博文首页 > 阳阳的博客：【leetcode.101】对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
?
例如，二叉树?[1,2,2,3,4,4,3] 是对称的。
但是下面这个?[1,2,2,null,3,null,3] 则不是镜像对称的:
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
所谓对称二叉树，即如下图所示：
那么，对于任意一对结点p、q，都有这样的性质：p.left.val=q.right.val，p.right.val=q.left.val
如果使用递归，我们大可以写出一个判断两个互为镜像位置的结点(p,q)的值是否相等的函数，然后在函数尾部递归调用，来判断镜像结点对(p.left，q.right)以及(p.right，q.left)是否满足性质。
递归终止条件为：
可以写出这样的代码：
//递归解决
public boolean isSymmetric(TreeNode root) {
if (root==null){
return true;
}
return check(root.left, root.right);
}
private boolean check(TreeNode p, TreeNode q) {
//两个结点都为null
if (p == null && q == null) {
return true;
}
//其中一个结点为null
if (p == null || q == null) {
return false;
}
//两个结点的值不相等
if (p.val != q.val) {
return false;
}
//继续判断p的左孩子与q的右孩子是否相等,p的右孩子与q的左孩子是否相等
return check(p.left, q.right) && check(p.right, q.left);
}如果n代表树中的结点总数，因为要遍历所有的结点，因此时间复杂度为O（n）
在最坏的情况下，树退化为链表，递归要进行n次，因此空间复杂度为O（n）
如果使用迭代来解决问题呢？
使用递归时，是先检查（p，q），再去检查（p.left，q.right）与（p.right，q.left）。
因此，我们大可以使用一个队列，首先将根节点的左右孩子分别入队
? ? ?循环每次取出连续的两个结点p，q，比较是否相等，接着将p.left、q.right、p.right、q.left入队（其实这里每次循环取出的两个结点都处于镜像位置上，因此只需要判断是否相等即可）
因此，可以写出这样的代码：
//迭代解决
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
LinkedList<TreeNode> linkedList = new LinkedList<>();
linkedList.add(root.left);
linkedList.add(root.right);
while (!linkedList.isEmpty()) {
TreeNode p = linkedList.removeFirst();
TreeNode q = linkedList.removeFirst();
//两个结点都为null
if (p == null && q == null) {
continue;
}
//其中一个结点为null
if (p == null || q == null) {
return false;
}
//两个结点的值不相等
if (p.val != q.val) {
return false;
}
//将处于镜像位置上的结点入队
linkedList.add(p.left);
linkedList.add(q.right);
linkedList.add(p.right);
linkedList.add(q.left);
}
return true;
}如果n代表树中的结点总数，因为要遍历所有的结点，因此时间复杂度为O（n）
这里使用队列，存储等待遍历的节点，且最大容量不会超过n，因此空间复杂度为O（n）
cs