对称二叉树
# 📃 题目描述
题目链接:
- 剑指 Offer 28. 对称的二叉树 (opens new window)
- 101. 对称二叉树 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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
# 🔔 解题思路
# 递归
递归三部曲
- 确定递归函数的参数和返回值
因为我们要比较的是根节点的两个子树是否是相互翻转的,进而判断这个树是不是对称树,所以要比较的其实就是根节点的两个子树,参数自然也是左子树节点和右子树节点。返回值自然是 boolean 类型。
代码如下:
bool compare(TreeNode* left, TreeNode* right)
- 确定终止条件
要比较两个节点(两棵树的根节点)数值相不相同(如果两棵树的根节点都不一样,那这两棵树一定不是对称的),首先要把两个节点为空的情况弄清楚!否则后面比较数值的时候就会操作空指针了。
节点为空的情况有:
- 左右都为空,对称,返回true
- 左节点为空,右节点不为空,或者左不为空,右为空,不对称,return false
此时已经排除掉了节点为空的情况,那么剩下的就是左右节点都不为空的情况:
- 左右都不为空,比较节点数值,不相同就 return false
此时左右节点不为空,且数值也不相同的情况我们也处理了。
最后,剩下的就是 left == right 的情况,可以开始判断这两棵子树是否对称了
- 确定单层递归的逻辑
此时才进入单层递归的逻辑,单层递归的逻辑就是处理 左右节点都不为空,且数值相同的情况。
- 比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
- 比较内侧是否对称,传入左节点的右孩子,右节点的左孩子。
- 如果左右都对称就返回 true ,有一侧不对称就返回 false
如上代码中,我们可以看出使用的遍历方式,左子树左右中,右子树右左中,所以我把这个遍历顺序也称之为 “后序遍历”(尽管不是严格的后序遍历)。
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return compare(root.left, root.right);
}
/**
* 判断 left 和 right 是否对称
* @param left root 左子树的根节点
* @param right root 右子树的根节点
* @return
*/
private boolean compare(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
// 剩下的就是 left 和 right 都不为 null 或者有一个为 null 的情况
else if (left == null || right == null) {
return false;
}
// 剩下的就是 left 和 right 都不为 null 的情况
else if (left.val != right.val) {
return false;
}
// 剩下的就是 left == right 的情况,可以开始判断这两棵子树是否对称了
// 1. 外侧节点(左子树的左节点,右子树的右节点)
boolean outside = compare(left.left, right.right);
// 2. 内侧节点(左子树的右节点,右子树的左节点)
boolean inside = compare(left.right, right.left);
return outside && inside;
}
}
# 迭代
这一题迭代的思路其实也很简单,通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等,成对地将左右子树中要比较的元素顺序放进一个队列中,如果相同则表示对称
代码如下:
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null && right == null) {
// 注意这是 continue 而不是 return true
continue;
}
// 剩下的就是 left 和 right 都不为 null 或者有一个为 null 的情况
else if (left == null || right == null) {
return false;
}
// 剩下的就是 left 和 right 都不为 null 的情况
else if (left.val != right.val) {
return false;
}
// 剩下的就是 left == right 的情况,直接入队进入下一轮处理
// 外侧节点成对入队
queue.offer(left.left);
queue.offer(right.right);
// 内侧节点成对入队
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
}
# 💥 复杂度分析
- 空间复杂度:递归和迭代法的空间复杂度都是 O(LogN),因为递归底层其实调用了栈空间
- 时间复杂度:递归和迭代法的时间复杂度相同,每个节点仅会被处理到两次,总的时间复杂度为 O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10