当前位置:网站首页>力扣101题:对称二叉树
力扣101题:对称二叉树
2022-07-06 11:35:00 【瀛台夜雪】
力扣101题:对称二叉树
题目描述
给你一个二叉树的根节点 root
, 检查它是否轴对称。
输入输出样例
输入:root = [1,2,2,3,4,4,3]
输出:true
输入:root = [1,2,2,null,3,null,3]
输出:false
算法一,使用递归
bool rootIsSymmetric(TreeNode *root1,TreeNode *root2)
{
bool leftTrue=false,rightTrue=false;
if(root1->val==root2->val)
{
if(root1->left&&root2->right)
{
leftTrue=rootIsSymmetric(root1->left,root2->right);
}
else if(!root1->left&&!root2->right)
{
leftTrue=true;
}
if(root1->right&&root2->left)
{
rightTrue=rootIsSymmetric(root1->right,root2->left);
}
else if(!root1->right&&!root2->left)
{
rightTrue=true;
}
return leftTrue&&rightTrue;
}
return false;
}
bool isSymmetric2(TreeNode *&root)
{
if(!root)
{
return true;
}
if(root->right&&root->left)
{
if(root->left->val==root->left->val)
{
return rootIsSymmetric(root->left,root->right);
}
return false;
}
else if(!root->left&&!root->right)
{
return true;
}
return false;
}
算法二,使用官方较为精简的递归
bool check(TreeNode *root1,TreeNode *root2)
{
if(!root1&&!root2)
{
return true;
}
if(!root1||!root2)
{
return false;
}
//将上面的几个条件判断合并到一块去了
return root1->val==root2->val&&check(root1->left,root2->right)&&check(root1->right,root2->left);
}
//官方较为简洁的递归算法
bool isSymmetric3(TreeNode *&root)
{
return check(root,root);
}
算法三,使用队列实现迭代
//解法三,使用迭代的思想,借助队列进行判断
bool isSymmetric4(TreeNode *&root)
{
if(!root)
{
return true;
}
if (!root->left&&!root->right)
{
return true;
}
//建立队列保存结点
queue<TreeNode *>que;
//将根节点的左孩子结点和右孩子结点入队
que.push(root->left);
que.push(root->right);
//并未验证下一个结点是否存在,只验证当前的结点是否存在
while(!que.empty())
{
//建立临时结点保存当前的结点
TreeNode *tempLeft=que.front();
que.pop();
TreeNode *tempRight=que.front();
que.pop();
//当两个结点都为空,继续循环,有一个为空则返回false
if(!tempLeft&&!tempRight)
{
continue;
}
if((!tempLeft||!tempRight)||(tempLeft->val!=tempRight->val))
{
return false;
}
//将两个结点的值分别入队
que.push(tempLeft->left);
que.push(tempRight->right);
que.push(tempLeft->right);
que.push(tempRight->left);
}
return true;
}
边栏推荐
- Live broadcast today | the 2022 Hongji ecological partnership conference of "Renji collaboration has come" is ready to go
- Camel case with Hungarian notation
- 包装行业商业供应链管理平台解决方案:布局智慧供应体系,数字化整合包装行业供应链
- Excel 中VBA脚本的简单应用
- 【翻译】云原生观察能力微调查。普罗米修斯引领潮流,但要了解系统的健康状况仍有障碍...
- LeetCode_双指针_中等_61. 旋转链表
- Low CPU load and high loadavg processing method
- Pychrm Community Edition calls matplotlib pyplot. Solution of imshow() function image not popping up
- Synchronous development of business and application: strategic suggestions for application modernization
- Meilu biological IPO was terminated: the annual revenue was 385million, and Chen Lin was the actual controller
猜你喜欢
学习探索-无缝轮播图
Mysql Information Schema 学习(一)--通用表
Synchronous development of business and application: strategic suggestions for application modernization
第五期个人能力认证考核通过名单公布
面试突击63:MySQL 中如何去重?
In depth analysis, Android interview real problem analysis is popular all over the network
DaGAN论文解读
PMP每日一练 | 考试不迷路-7.6
Swiftui game source code Encyclopedia of Snake game based on geometryreader and preference
今日直播 | “人玑协同 未来已来”2022弘玑生态伙伴大会蓄势待发
随机推荐
Analysis of frequent chain breaks in applications using Druid connection pools
终于可以一行代码也不用改了!ShardingSphere 原生驱动问世
Take a look at how cabloyjs workflow engine implements activiti boundary events
Cereals Mall - Distributed Advanced p129~p339 (end)
倒计时2天|腾讯云消息队列数据接入平台(Data Import Platform)直播预告
Elastic search indexes are often deleted [closed] - elastic search indexes gets deleted frequently [closed]
MySQL information Schema Learning (i) - - General table
RT-Thread 组件 FinSH 使用时遇到的问题
业务与应用同步发展:应用现代化的策略建议
LeetCode_格雷编码_中等_89.格雷编码
Interview assault 63: how to remove duplication in MySQL?
Solution of commercial supply chain management platform for packaging industry: layout smart supply system and digitally integrate the supply chain of packaging industry
[translation] Digital insider. Selection process of kubecon + cloudnativecon in Europe in 2022
[translation] a GPU approach to particle physics
C # - realize serialization with Marshall class
[玩转Linux] [Docker] MySQL安装和配置
Test technology stack arrangement -- self cultivation of test development engineers
Problems encountered in using RT thread component fish
五金机电行业智能供应链管理系统解决方案:数智化供应链为传统产业“造新血”
Graffiti intelligence is listed on the dual main board in Hong Kong: market value of 11.2 billion Hong Kong, with an annual revenue of 300 million US dollars