第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0331. 验证二叉树的前序序列化

题目地址(331. 验证二叉树的前序序列化)

题目描述

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。
_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

前置知识

  • 图论

公司

  • 暂无

思路

首先明确两点:
  1. 1.
    树是一种特殊的图,因此图的特性在树中也满足。
  2. 2.
    图中的点的入度总和 = 图中的点的出度总和。
稍微解释一下第二点:对于一个图来说,它是由点和边构成的。如果初始化图有 n 个点 ,接下来在 n 个点之间连接 m 条边。那么每连接一条边实际上整个图的入度和出度都增加一,因此任意中的入度和出度之和是相等的。
由于我们可以遍历前序遍历序列并计算入度和出度,一旦最后入度和出度不等,那么意味着肯定是不合法的。
如果入度和出度和相等,就一定是合法的么?也不一定。比如题目给出的示例三:"9,#,#,1"。因此我们需要额外判断在整个遍历过程出度是否小于入度,如果小于了,那么意味着不合法。(想想为什么?)
那么还需要别的判断么?换句话说,这就够了么?由于我们只需要判断入度和出度的相对关系,因此没有必要使用两个变量,而是一个变量表示二者的差值即可。
算法:
  • 初始化入度和出度的差值 diff 为 0
  • 遍历 preorder,遇到任何节点都要增加一个入度。 除此外,遇到非空节点增加两个出度。
  • 如果遍历过程 diff 非法可提前退出,返回 false
  • 最后判断 diff 是否等于 0

关键点

  • 从入度和出度的角度思考

代码

  • 语言支持:Python3
Python3 Code:
注意我最后判断的是 diff == -1 而不是 diff == 0,原因在于我代码利用了一个虚拟节点 dummy,dummy 直接指向了 root,其中 dummy 只有一个子节点,而不是两个(但是代码算成两个了)。这点需要大家注意,并不是和思路对不上。
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
diff = 0
for node in preorder.split(","):
diff -= 1
if diff < -1:
return False
if node != "#":
diff += 2
return diff == -1
复杂度分析
令 n 为数组长度。
  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

扩展

除此之外还有人给出了栈的解法,大家也可以参考下,作为思路扩展也是不错的。
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。