当前位置:网站首页>101. Symmetric Tree
101. Symmetric Tree
2022-04-23 09:57:00 【soO_007】
题目:
Given the root
of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3] Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3] Output: false
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]
. -100 <= Node.val <= 100
思路1:
判断一棵树是不是镜像对称。先用bfs里比较笨但是好理解的思路来了一遍。在按层遍历的基础上,增加一个存Treenode*的vector,把当前层的所有子都存进去,包括空子,然后将这个vector对称比较。比较分五种情况,假设左边的node为 com[i], 右边的node为com[j]:一是左右都为空,则对称;二是左空又不空,不对称;三是左不空右空,不对称;四是左右都不空但值不相等,不对称;五是左右都不空且值相等,则对称。只要是不对称的情况,直接返回false即可。这种多一个vector的解法比较好理解,就是多占空间复杂度。
代码1:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
while(q.size()) {
int len = q.size();
vector<TreeNode*> com;
for (int i = 0; i < len; i++) {
auto tmp = q.front();
q.pop();
com.push_back(tmp->left);
com.push_back(tmp->right);
if (tmp->left)
q.push(tmp->left);
if (tmp->right)
q.push(tmp->right);
}
for (int i = 0, j = com.size() - 1; i < com.size() / 2; i++, j--) {
if (!com[i] && !com[j])
continue;
if (com[i] && com[j] && com[i]->val == com[j]->val)
continue;
return false;
}
}
return true;
}
};
思路2:
dfs写法,我们已知上面讨论了的五种情况,那就是base case。不对称的情况直接返回false;而左右都空的情况下,我们是不需要往下递归的,因此也可以直接返回ture,最后一种左右不为空且值相等的情况,我们才继续递归。我们需要比较的外侧和内侧的子树,即左子的左子要和右子的右子相同,左子的右子和右子的左子相同,之后返回这两者结果的&&即可。
代码2:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return dfs(root->left, root->right);
}
private:
bool dfs(TreeNode* left, TreeNode* right) {
if (!left && !right)
return true;
else if (left && !right)
return false;
else if (!left && right)
return false;
else if (left->val != right->val)
return false;
bool waice = dfs(left->left, right->right);
bool neice = dfs(left->right, right->left);
return waice && neice;
}
};
版权声明
本文为[soO_007]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_49991368/article/details/124334486
边栏推荐
- Epidemic prevention registration applet
- Depth selector
- A concise course of fast Fourier transform FFT
- 计算机网络安全实验二|DNS协议漏洞利用实验
- 正大国际讲解道琼斯工业指数到底是什么?
- 论文阅读《Integrity Monitoring Techniques for Vision Navigation Systems》
- PHP notes (I): development environment configuration
- 杰理之有时候定位到对应地址的函数不准确怎么办?【篇】
- 一文读懂PlatoFarm新经济模型以及生态进展
- MapReduce核心和基础Demo
猜你喜欢
Depth selector
Redis 异常 read error on connection 解决方案
工业元宇宙平台规划与建设
Epidemic prevention registration applet
Yarn核心参数配置
Random neurons and random depth of dropout Technology
NEC infrared remote control coding description
SAP 03-amdp CDs table function using 'with' clause
Juc并发编程09——Condition实现源码分析
Nine abilities of agile manufacturing in the era of meta universe
随机推荐
SAP RFC_ CVI_ EI_ INBOUND_ Main BP master data creation example (Demo customer only)
【无标题】
第二章 Oracle Database In-Memory 体系结构(上) (IM-2.1)
Failureforwardurl and failureurl
MacOS下使用CLion编译调试MySQL8.x
通过流式数据集成实现数据价值(2)
LeetCode 1249. Minimum Remove to Make Valid Parentheses - FB高频题1
杰理之用户如何最简单的处理事件【篇】
Nine abilities of agile manufacturing in the era of meta universe
2022年流动式起重机司机考试题库模拟考试平台操作
自定义登录失败处理
通过流式数据集成实现数据价值(3)- 实时持续数据收集
ABAP CDs view with association example
SAP 03-amdp CDs table function using 'with' clause
Less than 100 secrets about prime numbers
[ACM-ICPC 2018 Shenyang Network preliminaries] J. Ka Chang (block + DFS sequence)
C language: expression evaluation (integer promotion, arithmetic conversion...)
[2020wc Day2] F. Clarice picking mushrooms (subtree and query, light and heavy son thought)
ABAP implementation publishes restful services for external invocation example
SAP CR transmission request sequence and dependency check