【leetcode】331. Verify Preorder Serialization of a Binary Tree
题目如下:
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as
#
._9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #For example, the above binary tree can be serialized to the string
"9,3,4,#,#,1,#,#,2,#,6,#,#"
, where#
represents a null node.Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.
Each comma separated value in the string must be either an integer or a character
'#'
representingnull
pointer.You may assume that the input format is always valid, for example it could never contain two consecutive commas such as
"1,,3"
.Example 1:
Input:"9,3,4,#,#,1,#,#,2,#,6,#,#"
Output:true
Example 2:
Input:"1,#"
Output:false
Example 3:
Input:"9,#,#,1"
Output:false
解题思路:我的方法是模拟树的遍历,依次pop出preorder中的节点存入queue中,用direction记录遍历的方向。direction=1表示往左子树方向的,等于2表示往右子树方向,遇到#号则变换一次方向。如果preorder的顺序是合法的,那么最后的结果一定是preorder和queue里面都是空。
代码如下:
class Solution(object):
def isValidSerialization(self, preorder):
"""
:type preorder: str
:rtype: bool
"""
if preorder == '#':
return True
elif preorder[0] == '#':
return False
preorder = preorder.split(',')
direction = 1
queue = [int(preorder.pop(0))]
while len(queue) > 0 and len(preorder) > 0:
item = preorder.pop(0)
if item == '#':
direction += 1
if direction % 3 == 0:
direction -= 1
queue.pop(-1)
continue
queue.append(item)
return len(preorder) == 0 and len(queue) == 0
最新文章
- 文本框focus之后高亮背景颜色
- ADO 连接数据库,取到VT_DATE型日期转换成 int型
- 多人开发Xcode工程冲突,打不开解决办法
- html页面的CSS、DIV命名规则
- ***PHP implode() 函数,将数组合并为字符串;explode() 函数,把字符串打散为数组
- android数据库持久化框架
- 初遇Git与MarkDown 文件
- web开发后端开源库收集
- Matlab人脸检測方法(Face Parts Detection)具体解释
- Scrapy学习之路(一)————环境配置
- 通过GPLOT过程制作图形
- JFrame添加组件
- lightgbm的sklearn接口和原生接口参数详细说明及调参指点
- SDN 第四次作业
- 【python】安装bcoding
- 通过IP获取所在城市
- CodeForces 17D Notepad(同余定理)
- 关于C语言中的Complex(复数类型)和imaginary(虚数类型)
- ovs加dpdk在日志中查看更多运行细节的方法
- OO第二次单元总结——电梯多线程调度问题
热门文章
- BUUCTF |Fakebook
- 攻防世界 | when_did_you_born
- 一些比较好的blogs
- How to not show unnecessary zeros when given integers but still have float answers when needed
- localhost和127.0.0.0
- JS-生成器函数(function 星号)的暂停和恢复(yield)
- JDK 5.0 新增解决线程安全 Callable接口和线程池
- SPSS详细教程:OR值的计算
- Win10.资料
- mooc-IDEA 调试代码--012