101. Symmetric Tree (Tree, Queue; DFS, WFS)
2024-08-26 20:07:12
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.
思路:要等到左儿子和右儿子的结果都知道了,才能判断当前节点的对称性,所以是后序遍历
法I:递归后序遍历
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if(!root) return true; bool result;
if((root->left==NULL && root->right != NULL) ||(root->left!=NULL && root->right == NULL))
{
return false;
}
else if(root->left == NULL && root->right == NULL)
{
return true;
}
else
{
result = cmp(root->left, root->right);
}
}
bool cmp(TreeNode * node1, TreeNode* node2)
{
int result1 = true;
int result2 = true;
if(node1->val!=node2->val) return false;
else
{
//递归结束条件:至少有一个节点为NULL
if((node1->left==NULL && node2->right != NULL) ||
(node1->left!=NULL && node2->right == NULL)||
(node1->right!=NULL && node2->left == NULL)||
(node1->right==NULL && node2->left != NULL))
{
return false;
}
if((node1->left == NULL && node2->right == NULL)&&
(node1->right == NULL && node2->left== NULL))
{
return true;
} //互相比较的两个点,要比较节点1的左儿子和节点2的右儿子,以及节点1的右儿子和节点2的左儿子
if(node1->left != NULL)
{
result1 = cmp(node1->left,node2->right);
}
if(node1->right != NULL)
{
result2 = cmp(node1->right,node2->left);
}
return (result1 && result2);
}
}
};
法II:用队列实现层次遍历(层次遍历总是用队列来实现)
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if(root == NULL) return true;
queue<TreeNode*> q;
q.push(root->left);
q.push(root->right);
TreeNode *t1, *t2;
while(!q.empty()){
t1 = q.front();
q.pop();
t2 = q.front();
q.pop();
if(t1 == NULL && t2 == NULL)
continue;
if(t1 == NULL || t2 == NULL || t1->val != t2->val)
return false;
q.push(t1->left);
q.push(t2->right);
q.push(t1->right);
q.push(t2->left);
}
return true;
}
};
最新文章
- PHPCMS调用点击量的方法
- OpenCV2邻域和模板操作
- sass跨文件重写变量
- 【转】关系映射文件***.hbm.xml详解
- PSR-4——新鲜出炉的PHP规范
- 释放SQL Server占用的内存
- android中获取root权限的方法以及原理(转)
- Codeforces 191 C Fools and Roads (树链拆分)
- iptables惹的祸
- iOS开发——判断是否第一次启动
- @OnetoOne @OnetoMany @ManyToOne(2)
- Oracle 11g Articles
- python 启动shell报错 Subprocess Startup Error
- Windows 2012 安装 SQL Server 2012,.Net Framework 3.5安装不成的解决办法
- java 中数据的强制转换 和计算的补码运算
- html 语法
- Dos命令下目录操作
- Android Studio怎么文件添加到收藏和打开收藏夹
- windows下用wubi快速安装ubuntu
- python内置函数和魔法函数
热门文章
- Beta阶段第1周/共2周 Scrum立会报告+燃尽图 07
- chrome 49 版本bug: flex父元素设置flex:1 , 子元素用height:100%无法充满父元素
- dir listing 目录文件列表索引
- I.MX6 GPS Android HAL Framework 调试
- 2018-2019-1 20165212 《信息安全系统设计基础》第八周学习总结(pwd)
- element-ui打包和运行报错处理
- ASP.NET MVC3默认提供了11种ActionResult的实现
- nexus 使用Raw Repositories 进行maven site 发布
- phpmyadmin不允许一个表创建多个主键的解决办法
- django创建第一个项目helloworld