☆打卡算法☆LeetCode 101、对称二叉树 算法解析
☆打卡算法☆LeetCode 101、对称二叉树 算法解析
恬静的小魔龙
发布于 2022-08-07 10:23:43
发布于 2022-08-07 10:23:43
一、题目
1、算法题目
“给定二叉树的根节点，检查它是否轴对称。”
题目链接：
来源：力扣（LeetCode）
链接：101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
image.png
示例 1：
输入： root = [1,2,2,3,4,4,3]
输出： true示例 2：
输入： root = [1,2,2,null,3,null,3]
输出： false二、解题
1、思路分析
这道题是检查二叉树是否轴对称，如果这个树的左右子树镜像对称，那么这个树是对称的。
因此，可以将问题转化为，两个树在什么条件下互为镜像：
- 两个跟节点具有相同的值。
- 每个树的右子树都与另一个树的左子树镜像对称。
那么就可以编写一个递归函数，通过两个指针来遍历这棵树，指针开始都指向树的根，随后p指针向右，q指针向左；q指针向右，p指针向左。
每次先检查节点的值是否相同，再判断左右子树是否对称。
2、代码实现
代码参考：
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
image.png
3、时间复杂度
时间复杂度 ： O(n)
遍历了这棵树，时间复杂度为O(n)。
空间复杂度： O(n)
递归层数不超过n，空间复杂度为O(n)。
三、总结
我们使用递归的方法实现了对对称性的判断。
首先，判断根节点的值，然后判断左右子树的值是否相等，然后判断结构是否相同。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-02-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录