代码随想录刷题day40|（二叉树篇）101.对称二叉树
目录
一、二叉树基础知识
二、对称二叉树思路
2.1 递归法
2.2 迭代法
三、相关算法题目
四、易错点
4.1 递归法判断终止条件
4.2 迭代法左右节点均为空的处理
4.3 迭代法队列的实现类
一、二叉树基础知识
详见：代码随想录刷题day34|（二叉树篇）二叉树的递归遍历-CSDN博客
二、对称二叉树思路
递归比较左右子树：
- 左子树的左节点和右子树的右节点比较；
- 左子树的右节点和右子树的左节点比较；
2.1 递归法
1.确定递归函数的参数和返回值：左右两个结点，返回值boolean；
2.确定终止条件：分情况讨论，比较两个结点值相不相等，首先要先判断两个结点是否为空结点，否则直接比较值会有空指针异常的报错；
结点为空的情况有：
- 左右节点均为空，对称，返回true；
- 左节点不为空，右节点为空，不对称，返回false；
- 左节点为空，右节点不为空，不对称，返回false；
- 左右节点均不为空，但是节点值不相等，不对称，返回false；
3.确定递归单层逻辑：
如果以上几种终止条件均不满足，说明左右节点均不为空，且结点值相同，那么进入下一层递归，比较左右两个结点的孩子结点：
- 比较左节点的左孩子和右节点的右孩子；
- 比较左节点的右孩子和右节点的左孩子；
- 如果以上两次递归结果均为true，则返回true；
2.2 迭代法
模拟递归的过程：
使用一个普通队列来存放待处理结点，多个 if 条件分别处理结点为空的情况；
如果结点不为空且结点值相等的话，依次将左节点的左孩子、右节点的右孩子、左节点的右孩子、右节点的左孩子加入队列，每次从队列中弹出两个节点（左子树的节点和右子树的节点），并比较它们的值，不断循环上述过程；
三、相关算法题目
101.对称二叉树
递归法：
class Solution {
public boolean isSymmetric(TreeNode root) {
//递归法
if(root == null) return true;
return isEqual(root.left, root.right);
}
public boolean isEqual(TreeNode left, TreeNode right){
if(left == null && right == null){//左右结点均为空
return true;
}else if(left != null && right == null){//左结点不为空 右节点为空
return false;
}else if(left == null && right != null){//左节点为空 右节点不为空
return false;
}else if(left.val != right.val){//左右结点均不为空 但结点值不等
return false;
}else{//左右结点均不为空 且结点值相同 此时才能进入下一层递归
boolean outside = isEqual(left.left, right.right);
boolean inside = isEqual(left.right, right.left);
return outside && inside;
}
}
}注：判断终止条件的时候易错点▲ 见4.1
迭代法：
class Solution {
public boolean isSymmetric(TreeNode root) {
//迭代法 使用普通队列
Deque<TreeNode> deque = new LinkedList<>();//⚠️ 不能用ArrayDeque
if(root == null) return true;
//deque.offer(root);
deque.offer(root.left);
deque.offer(root.right);
while(!deque.isEmpty()){
TreeNode left = deque.poll();
TreeNode right = deque.poll();
if(left == null && right == null){
//return true;
continue;
}else if(left != null && right == null){
return false;
}else if(left == null && right != null){
return false;
}else if(left.val != right.val){
return false;
}else{
deque.offer(left.left);
deque.offer(right.right);
deque.offer(left.right);
deque.offer(right.left);
}
}
return true;
}
}
四、易错点
4.1 递归法判断终止条件
正确：👇
if(left == null && right == null){
return true;
}else if(left != null && right == null){
return false;
}else if(left == null && right != null){
return false;
}错误：👇
if(left == null && right == null){
return true;
}else if(left != null || right != null){
return false;
}第一个 if 不满足，判断下面else if中的条件时，如果此时 left 和 right 都不为空，按照错误写法，符合条件（左不为空 或者 右不为空，两者满足其一）返回false了；
所以左右结点有一个不为空的条件需要分开写；
PS：如果 != 改成 ==，这样写是可行的；
4.2 迭代法左右节点均为空的处理
if(left == null && right == null){
//return true;
continue;
}return true；❌ continue；✅
这只是当前两个节点为空，不代表整个树对称，应该使用 continue 跳过当前循环，继续检查队列中的其他节点。
4.3 迭代法队列的实现类
Deque<TreeNode> deque = new ArrayDeque<>(); ❌
Deque<TreeNode> deque = new LinkedList<>(); ✅
ArrayDeque 是基于数组实现的双端队列，不允许存储 null 值，所以会抛出 NullPointerException异常；
LinkedList是基于链表实现的双端队列，允许存储 null 值；