【LeetCode】101. Symmetric Tree (2 solutions)
2024-09-22 01:48:12
Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
不管是递归还是非递归,找到关系就好做。
所谓对称,也就是:
1、left对应right
2、left->left对应right->right
3、left->right对应right->left
解法一:递归
/**
* Definition for binary tree
* 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 isSymTree(root->left, root->right);
}
bool isSymTree(TreeNode* p, TreeNode* q)
{
if(!isSameNode(p, q))
return false;
if(!p && !q)
return true;
return isSymTree(p->left, q->right) && isSymTree(p->right, q->left);
}
bool isSameNode(TreeNode* p, TreeNode* q)
{
if(!p && !q)
return true;
if((!p && q) || (p && !q) || (p->val != q->val))
return false;
return true;
}
};
解法二:非递归
使用两个队列,对左右子树分别进行层次遍历。
进队时的对应元素比较即可。
/**
* Definition for binary tree
* 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; if(!isSameNode(root->left, root->right))
return false;
if(!root->left && !root->right)
return true; queue<TreeNode*> lqueue;
queue<TreeNode*> rqueue;
lqueue.push(root->left);
rqueue.push(root->right);
while(!lqueue.empty() && !rqueue.empty())
{
TreeNode* lfront = lqueue.front();
TreeNode* rfront = rqueue.front();
lqueue.pop();
rqueue.pop(); if(!isSameNode(lfront->left, rfront->right))
return false;
if(lfront->left && rfront->right)
{
lqueue.push(lfront->left);
rqueue.push(rfront->right);
} if(!isSameNode(lfront->right, rfront->left))
return false;
if(lfront->right && rfront->left)
{
lqueue.push(lfront->right);
rqueue.push(rfront->left);
}
}
return true;
}
bool isSameNode(TreeNode* p, TreeNode* q)
{
if(!p && !q)
return true;
if((!p && q) || (p && !q) || (p->val != q->val))
return false;
return true;
}
};
最新文章
- zapewnia stale poprawiając relacje związane
- Material Design学习笔记
- 《利用python进行数据分析》读书笔记--第八章 绘图和可视化
- 之三:CAAnimationGroup - 动画组
- 1103简单SQL 行转列思路
- spring mvc 初始化错误
- HDOJ(1010)DFS+剪枝
- 数组、单链表和双链表介绍 以及 双向链表的C/C++/Java实现
- web.xml中webAppRootKey
- jQuery两个列表中元素相互交换Demo
- 转载--C++中struct与class
- iOS关于时间的处理
- 没人看系列----css 随笔
- Java(16)接口
- centos7/rhel7安装较高版本ruby2.2/2.3/2.4+
- 【python】python为何多线程无法切换
- Unity 脚本中的主要函数的 执行顺序及其介绍
- [转帖]PG的简单备份恢复 找时间进行测试
- 【CentOS】CentOS7.0 mysql与卸载
- JavaScrpt简单介绍
热门文章
- zoj 1610 Count the Colors 线段树区间更新/暴力
- CentOS 6.9通过RPM安装EPEL源(http://dl.fedoraproject.org)
- linux下的系统调用函数到内核函数的追踪
- Assembly.Load()方法,Assembly.LoadFrom()方法,Assembly.LoadFile()方法的区别!
- Eclipse 中导入jar包
- 使用maven的profile切换项目各环境的参数
- 常用EDA工具环境变量配置
- HTML5 input file控件使用accept过滤限制的文件类型以及在谷歌下打开很慢的问题
- Cognos开发ContentManagerServiceStub不能转换为Stub
- TortoiseSVN 源代码下载