《剑指offer》面试题28. 对称的二叉树
2024-10-18 23:42:06
问题描述
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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
代码(递归)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)return true;
return fun(root->left,root->right);
}
bool fun(TreeNode* node1,TreeNode* node2)
{
if(!node1 && node2)return false;
if(node1 && !node2)return false;
if(!node1 && !node2)return true;
if(node1->val != node2->val)return false;
return fun(node1->left,node2->right) && fun(node1->right,node2->left);
}
};
结果：
执行用时 :4 ms, 在所有 C++ 提交中击败了92.33%的用户
内存消耗 :16.4 MB, 在所有 C++ 提交中击败了100.00%的用户
代码(非递归)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)return true;
queue<TreeNode*> q1,q2;
q1.push(root->left);
q2.push(root->right);
while(!q1.empty() && !q2.empty())
{
TreeNode* node1,*node2;
node1 = q1.front();q1.pop();
node2 = q2.front();q2.pop();
if(!node1 && node2)return false;
if(node1 && !node2)return false;
if(!node1 && !node2)continue;
if(node1->val != node2->val)return false;
q1.push(node1->left);q1.push(node1->right);
q2.push(node2->right);q2.push(node2->left);//注意顺序
}
return true;
}
};
结果：
执行用时 :12 ms, 在所有 C++ 提交中击败了33.23%的用户
内存消耗 :16.9 MB, 在所有 C++ 提交中击败了100.00%的用户
最新文章
- Linux(三)__文件权限、系统的查找、文本编辑器
- android wifi 获取扫描结果
- Java读写文件通用格式
- swift 定制自己的Button样式
- Webpack使用教程二
- (转)QRCODE二维码介绍及常用控件推荐
- Intellij IDEA 导入Eclipse或MyEclipse的Web项目(旧版 转载)
- Codeforces 527D Clique Problem
- 用Iconv应对NodeJs对称加密技术在汉字编码与NoSQL的一些坑洞
- ECSTORE1.2系统更改后台密码
- DateTime格式
- Java中的双重检查锁（double checked locking）
- [Luogu3527][POI2011]MET-Meteors
- prev_permutation(a+1,a+n+1)
- There is no session with id XXX
- requirejs案例
- zabbix 报警方式之 邮件报警（4）
- Web API使用记录系列（二）HelpPage优化与WebApiTestClient
- JavaScript经常使用代码段
- maven学习5 构建MyBatis项目