当前位置:网站首页>leetcode:331. 验证二叉树的前序序列化
leetcode:331. 验证二叉树的前序序列化
2022-08-09 22:01:00 【OceanStar的学习笔记】
题目来源
题目描述
class Solution {
public:
bool isValidSerialization(string preorder) {
}
};
题目解析
栈
为什么可以用栈
- 我们知道[前序遍历]是按照[根节点-左子树-右子树]的顺序遍历的,只有当根节点的所有左子树遍历完成之后,才会遍历右子树。
- 所以我们可以先判断【左子树】是否有效,【右子树】是否有效,最后判断【根节点-左子树-右子树】是否有效。
- 这个思路类似递归,而把递归改写成循环时,就会使用「栈」,这就是本题使用「栈」的原因。
如何判断一颗树是否有效?
首先考虑最简单的情况:怎么判断一个节点是叶子节点。很明显,当一个节点的两个孩子都是#
的时候,该节点就是叶子节点
当一个节点不是叶子节点时,那么它必定至少有一个孩子非空!有两种情况
- 两个孩子都非
#
- 一个孩子为
#
,一个孩子不为#
为了兼容这两种情况,我们可以把有效的叶子节点使用#
替代,此时叶子节点会变成空节点。
如输入: “9,3,4,#,#,1,#,#,2,#,6,#,#” ,当遇到 x,#,# 的时候,就把它变为 #。
模拟一遍过程:
- [9,3,4,#,#] => [9,3,#],继续
- [9,3,#,1,#,#] => [9,3,#,#] => [9,#] ,继续
- [9,#2,#,6,#,#] => [9,#,2,#,#] => [9,#,#] => [#],结束
也就是说:
- 栈顶有两个"#“的时候,连续弹出这两个”#“以及它们的共同父节点,然后将一个”#"入栈。
- 也就是用空节点代替一棵子树。
- 最终栈中只有一个
#
class Solution {
public:
bool isValidSerialization(string preorder) {
std::vector<std::string> stk;
std::stringstream ss(preorder); // 使用 stringstream与getline 分割字符串
string tmp;
while (getline(ss, tmp, ',')){
// 使用 stringstream与getline 分割字符串
stk.push_back(tmp);
int len = stk.size();
// 用「#」替换 「数字##」
while (len >= 3
&& stk[len - 1] == "#"
&& stk[len - 2] == "#"
&& stk[len - 3] != "#"){
stk.pop_back();
stk.pop_back();
stk.pop_back();
stk.emplace_back("#");
len = stk.size();
}
}
// 如果最后模拟栈中只剩一个#,说明是合法的序列
return stk.size() == 1 && stk[0] == "#";
}
};
计算入度出度
如果存在一条有向边 A --> B,则这条边给 A 增加了 1 个出度,给 B 增加了 1 个入度。
类似题目
边栏推荐
- Activiti7审批流
- [Microservice~Nacos] Nacos service provider and service consumer
- L3-2 Delete up to three characters (30 points)
- Jinshanyun earthquake, the epicenter is in bytes?
- 肝通宵写了三万字把SQL数据库的所有命令,函数,运算符讲得明明白白讲解,内容实在丰富,建议收藏+三连好评!
- 【EF】 更新条目时出错。有关详细信息,请参见内部异常。[通俗易懂]
- The kvm virtual machine cannot be started, NOT available, and the PV is larger than the partition
- Interviewer: How to deal with Redis big key?
- 接口自动化测试实践指导(上):接口自动化需要做哪些准备工作
- SecureCRT background color
猜你喜欢
华为鸿蒙3.0的野望:技术、应用、生态
反射机制篇
Domestic mobile phone manufacturers once fought for it, but now it is the first to collapse...
FileZilla搭建FTP服务器图解教程
Quotefancy ,提供鼓舞人心语录的壁纸网站 - 倾城之链
Flask introductory learning tutorial
一文让你快速了解隐式类型转换【整型提升】!
Kubernetes Service对象
shell学习
Xiaohei leetcode's refreshing rainy day trip, just finished eating Yufei Beef Noodles, Mala Tang and Beer: 112. Path Sum
随机推荐
Deceptive Dice
你真的了解乐观锁和悲观锁吗?
Liver all night to write a thirty thousand - word all the commands the SQL database, function, speaks clearly explain operators, content is rich, proposal collection + 3 even high praise!
A1. Prefix Flip (Easy Version)
面试官:Redis 大 key 要如何处理?
【软考 系统架构设计师】案例分析⑤ 质量属性和架构评估
Chatting embarrassing scenes, have you encountered it?Teach you to get the Doutu emoticon package with one click, and become a chat expert
Socket发送缓冲区接收缓冲区快问快答
AI+Medical: Using Neural Networks for Medical Image Recognition and Analysis
第 1 章 一大波数正在靠近——排序
B. Neighbor Grid
Leetcode.25 K个一组翻转链表(模拟/递归)
JS–比想象中简单
Converting angles to radians
“稚晖君”为2022昇腾AI创新大赛打call&nbsp;期待广大开发者加入
[Microservice~Nacos] Configuration Center of Nacos
Bean life cycle
级联下拉菜单的实现「建议收藏」
navicat 快捷键
js array object deduplication