331 Verify Preorder Serialization of a Binary Tree 验证二叉树的前序序列化
2024-09-06 16:16:47
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录这个节点的值。如果它是一个空节点,我们可以使用一个标记值,例如 #。
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
例如,上面的二叉树可以被序列化为字符串"9,3,4,#,#,1,#,#,2,#,6,#,#",其中#代表一个空节点。
给定一串以逗号分隔的值,验证它是否是正确的二叉树的前序序列化。想出一种在不重构树的情况下的可行算法。
每个逗号分隔的字符串中的值肯定是一个整数或者一个表示null指针的'#'。
你可以假定输入格式总是有效的,例如它永远不能包含两个连续的逗号,比如"1,,3"。
示例 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
返回 true
示例 2:
"1,#"
返回 false
示例 3:
"9,#,#,1"
返回 false
详见:https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/description/
C++:
class Solution {
public:
bool isValidSerialization(string preorder) {
istringstream in(preorder);
vector<string> v;
string t = "";
int cnt = 0;
while (getline(in, t, ','))
{
v.push_back(t);
}
for (int i = 0; i < v.size() - 1; ++i)
{
if (v[i] == "#")
{
if (cnt == 0)
{
return false;
}
--cnt;
}
else
{
++cnt;
}
}
return cnt == 0 && v.back() == "#";
}
};
参考:https://www.cnblogs.com/grandyang/p/5174738.html
最新文章
- Uncaught ReferenceError: WebForm_DoPostBackWithOptions is not defined
- Powershell 学习笔记【持续更新】
- perl 对源文件内容修改 方法整理
- 基于 Markdown 的开源的 Node.js 知识库平台
- yoman安装和使用
- javascript 原型及继承
- hdu1158 dp经典题
- Nodejs之WebSocket
- eclipse Ctrl +左键查看源代码Source not found
- 安装MYSQL 出现Error 1045 access denied 的解决方法
- Fiddler 抓包 教程
- mysql错误号码:1129
- 常用的连接字符串(vs中连接sqlserver)方便随时查看
- SQL 2008 数据库迁移
- photoshop的页面制作练习2
- eclipse从git拉去出现红色方块的解决办法
- Python 地点转化为经纬度
- AGV
- DAY06、元组、字典、集合
- 【CF724F】Uniformly Branched Trees 动态规划
热门文章
- PAT 1129 Recommendation System
- 【Lqb T336】Cowboys
- linux常用命令大全(linux基础命令+命令备忘录+面试复习)
- [luoguP1156] 垃圾陷阱(DP)
- ECMAScript 6 入门学习笔记(零)——开始
- 洛谷 P2683 小岛
- I/O 模型及其设计模式
- 1.求整数最大的连续0的个数 BinaryGap Find longest sequence of zeros in binary representation of an integer.
- Solid Edge如何制作装配体的剖视图
- LINQ体验(11)——LINQ to SQL语句之Null语义和String/DateTime方法