当前位置:网站首页>Li Kou 101: symmetric binary tree
Li Kou 101: symmetric binary tree
2022-07-06 19:36:00 【Yingtai night snow】
Power button 101 topic : Symmetric binary tree
Title Description
Give you the root node of a binary tree root
, Check whether it is axisymmetric .
I/o sample
Input :root = [1,2,2,3,4,4,3]
Output :true
Input :root = [1,2,2,null,3,null,3]
Output :false
Algorithm one , Using recursion
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;
}
Algorithm 2 , Use the official simpler recursion
bool check(TreeNode *root1,TreeNode *root2)
{
if(!root1&&!root2)
{
return true;
}
if(!root1||!root2)
{
return false;
}
// Combine the above conditional judgments
return root1->val==root2->val&&check(root1->left,root2->right)&&check(root1->right,root2->left);
}
// The official relatively simple recursive algorithm
bool isSymmetric3(TreeNode *&root)
{
return check(root,root);
}
Algorithm three , Use queues to implement iterations
// Solution 3 , Use the idea of iteration , Use the queue to judge
bool isSymmetric4(TreeNode *&root)
{
if(!root)
{
return true;
}
if (!root->left&&!root->right)
{
return true;
}
// Create a queue save node
queue<TreeNode *>que;
// Join the left child node and the right child node of the root node
que.push(root->left);
que.push(root->right);
// The existence of the next node is not verified , Only verify whether the current node exists
while(!que.empty())
{
// Create a temporary node to save the current node
TreeNode *tempLeft=que.front();
que.pop();
TreeNode *tempRight=que.front();
que.pop();
// When both nodes are empty , Continue to cycle , If one is empty, it returns false
if(!tempLeft&&!tempRight)
{
continue;
}
if((!tempLeft||!tempRight)||(tempLeft->val!=tempRight->val))
{
return false;
}
// Queue the values of two nodes respectively
que.push(tempLeft->left);
que.push(tempRight->right);
que.push(tempLeft->right);
que.push(tempRight->left);
}
return true;
}
边栏推荐
- 时钟轮在 RPC 中的应用
- A popular explanation will help you get started
- PMP practice once a day | don't get lost in the exam -7.6
- 10 schemes to ensure interface data security
- Leetcode topic [array] - 119 Yang Hui triangle II
- Solution of intelligent management platform for suppliers in hardware and electromechanical industry: optimize supply chain management and drive enterprise performance growth
- 【pytorch】yolov5 训练自己的数据集
- 350. 两个数组的交集 II
- Detailed idea and code implementation of infix expression to suffix expression
- LeetCode_ Double pointer_ Medium_ 61. rotating linked list
猜你喜欢
Analysis of rainwater connection
凤凰架构3——事务处理
学习探索-无缝轮播图
Low CPU load and high loadavg processing method
利用 clip-path 绘制不规则的图形
安装Mysql报错:Could not create or access the registry key needed for the...
Countdown 2 days | live broadcast preview of Tencent cloud message queue data import platform
【计算情与思】扫地僧、打字员、信息恐慌与奥本海默
The second day of rhcsa study
Mysql Information Schema 学习(二)--Innodb表
随机推荐
PMP每日一练 | 考试不迷路-7.6
【基础架构】Flink/Flink-CDC的部署和配置(MySQL / ES)
[pytorch] yolov5 train your own data set
时钟轮在 RPC 中的应用
Take a look at how cabloyjs workflow engine implements activiti boundary events
121. 买卖股票的最佳时机
[translation] supply chain security project in toto moved to CNCF incubator
Excel 中VBA脚本的简单应用
Low CPU load and high loadavg processing method
Learning and Exploration - function anti shake
A popular explanation will help you get started
Teach you to learn JS prototype and prototype chain hand in hand, a tutorial that monkeys can understand
Sanmian ant financial successfully got the offer, and has experience in Android development agency recruitment and interview
Live broadcast today | the 2022 Hongji ecological partnership conference of "Renji collaboration has come" is ready to go
潇洒郎: AttributeError: partially initialized module ‘cv2‘ has no attribute ‘gapi_wip_gst_GStreamerPipe
DaGAN论文解读
打家劫舍III[后序遍历与回溯+动态规划]
Don't miss this underestimated movie because of controversy!
Learning and Exploration - Seamless rotation map
Benefit a lot, Android interview questions