【一天一道Leetcode】验证二叉树的前序序列化

看那个码农

共 2038字,需浏览 5分钟

 ·

2021-03-14 18:34


本篇推文共计2000个字,阅读时间约3分钟。



01


题目描述


题目描述:


给定一串以逗号分隔的序列,

验证它是否是正确的二叉树的前序序列化

编写一个在不重构树的条件下的可行算法。


序列化二叉树的一种方法是使用前序遍历。

当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。



例如,上面的二叉树可以被序列化为
字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"
其中 # 代表一个空节点。


每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如"1,,3"。


示例:

输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

输入: "1,#"
输出: false

输入: "9,#,#,1"
输出: false




02


方法和思路


我们可以用入度和出度的方法来解决本题。

 

所有节点的入度之和等于出度之和。

 

可以根据这个特点来判断输入序列是否为有效的。


我们用一个例子解释上面的意思,

如下图所示,是一个二叉树:



节点1的出度为2,入度为0
节点2,5的出度为2,入度为1
节点3,4,6,7的出度为2,入度为1
空节点#的出度为0,入度为1
所有节点的出度和为14
所有节点的入度和为14


即二叉树中所有节点的入度之和等于出度之和


我们只要把字符串利用遍历的方式,遍历一次,
计算每个节点的出度和入度之差diff,
即diff=出度-入度

在遍历到任何一个节点的时候,

要求diff>=0,原因是还没遍历到该节点的子节点,
所以此时的出度应该大于等于入度。

如果diff<0,则代表出度<入度。此时二叉树不成立,返回False





我们用代码表示此题的解法如下:

class Solution(object):
    def isValidSerialization(self, preorder):
        nodes = preorder.split(',')
        diff = 1
        for node in nodes:
            diff -= 1
            if diff < 0:
                return False
            if node != '#':
                diff += 2
        return diff == 0


为什么上面的代码中 diff 的初始化为 1:

因为,我们加入一个非空节点时,
都会先减去一个入度,再加上两个出度。

但是由于根节点没有父节点,所以其入度为 0,出度为 2。

因此 diff 初始化为 1,
是为了在加入根节点的时候,
先减去一个入度,再加上两个出度,此时 diff 正好应该是2.





往期回顾

【年终总结】你好2021,再见2020。


【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台


【秋招纪实录】一篇特别正经的【腾讯】求职经验分享


【一天一道Leetcode】回文字符串-最少分割次数


【一天一道Leetcode】用栈实现队列


【一天一道Leetcode】套信封问题



☆ END ☆

你与世界

只差一个

公众号

浏览 30
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报