【剑指Offer】面试题28. 对称的二叉树
2024-09-02 08:24:21
题目
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
限制：
0 <= 节点个数 <= 1000
思路一：递归
利用镜像。
代码
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return isMirror(root, root);
}
bool isMirror(TreeNode *root, TreeNode *copy) {
if (!root && !copy) return true;
if (!root || !copy) return false;
if (root->val == copy->val) {
return isMirror(root->left, copy->right) && isMirror(root->right, copy->left);
}
return false;
}
};
思路二：迭代
将树的左右节点按相关顺序插入队列中，判断队列中每两个节点是否相等。
代码
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
queue<TreeNode*> que;
que.push(root);
que.push(root);
while (!que.empty()) {
TreeNode *node1 = que.front();
que.pop();
TreeNode *node2 = que.front();
que.pop();
if (!node1 && !node2) continue;
if (!node1 || !node2 || node1->val != node2->val) return false;
que.push(node1->left);
que.push(node2->right);
que.push(node1->right);
que.push(node2->left);
}
return true;
}
};
最新文章
- 查看mysql数据库版本方法总结
- [问题记录.VisualStudio]TFS项目映射问题解决
- 修复 XE8 Win 平台 Firemonkey Memo 卷动后会重叠的问题
- poj1279 半平面交
- LeetCode——Rotate Image（二维数组顺时针旋转90度）
- Quartz.NET配置
- jstl标签用法
- springboot源码解析 - 构建SpringApplication
- 一位Erlang程序猿的自白
- java package and import
- Android开发之手势滑动（滑动手势监听）详解
- Alyona and a tree
- php实现获取汉字的首字母
- iKcamp团队制作｜基于Koa2搭建Node.js实战（含视频）☞ 中间件用法
- linux如何安装java环境
- 【BZOJ1969】航线规划（Link-Cut Tree）
- ubuntu18.04使用SPFlashTool提示缺少libpng12.so.0
- Nginx 动静分离
- python Com接口测试
- windows time-wait 问题处理记录