331. 验证二叉树的前序序列化
描述
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。
例如,上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # 代表一个空节点。
给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如 "1,,3" 。
示例
示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:输入: "1,#"
输出: false
示例 3:输入: "9,#,#,1"
输出: false
分析
二叉树的题目其实蕴含很多的规律公式,如果熟悉二叉树的话很容易得到想到这个题的一些思路。
二叉树有这样的规律:
若度为2的节点有n个,则叶子节点(度为0的节点)有n+1个。
这个规律其实是通过数学归纳法得来的,如下图:
其实由上面的图例不难发现这样一个规律,每当增加一个叶子节点,有两种情况:
- 叶子节点A本身是在叶子节点B上增加的,那么相当于B的叶子节点状态转移到A上了,叶子节点数没有变化。
- 叶子节点A本身实在度为1的节点上增加的,那么增加之后,叶子节点数+1,度为2的节点数+1。
如果能理解上述的一个规律变化,那么再来看今天的这个题目,其实不就是把叶子节点转化成了#吗?
而且今天的题目特殊,没有度为1的节点,所有的节点都必须是满的,在先序扫描的时候,就存在这样的关系:
- "#"的数量比数的数量多1;
- 先序序列,根左右往后遍历,最后的一个值一定是#;
- 任何时候,#的数量不能多于数字的数量。
实现
依照上述分析,我们应该能想到如下的实现:(一些题解使用栈,完全没必要,费时费力)
- 使用一个标记值flag存储当前的一个序列数;
- 当遇到一个数字,那么flag+1
- 当遇到一个#号,那么应该有如下的判断:
- 如果flag=0,说明之前没有数字了
- 判断当前的#是不是序列的最后一个,是,那么返回序列正确
- 不是,那么返回序列错误
- 如果flag!=0,那么flag-1
- flag为什么-1
- 参照之前分析里面的图例,每增加一个#,相当于和之前的序列进行了一次抵消
- 如果遇到一个,号,那么不做处理,判断下一个字符
- 如果字符序列遍历完了还没得到结果,说明字符序列是错的
代码
func isValidSerialization(preorder string) bool {
n := len(preorder)
if n == 0 {
// 如果序列长度为0,返回一个false
// 注,如果表示空节点,那么应该至少有一个#,所以序列长度为0是false
return false
}
// 记录数字数,和#抵消
flag := 0
for i := 0; i < n; {
// 如果是逗号,不做处理
if preorder[i] == ',' {
i++
}
if preorder[i] == '#' {
// flag=0,说明数字全部被抵消了,那么就应该判断当前的#是否是最后一个
if flag == 0 {
// i=n-1表示最后一个,!=表示非最后一个
return i == n-1
} else {
// 数字没有被抵消完,那么当前的#去抵消一个数字
flag--
}
i++
} else {
// 当前字符不是逗号,不是#号,就只能是数字了
// 注意一个坑,数字可能不止一个字符,比如10,所以要进行循环判断(我踩了一次坑)
for i < n && preorder[i] != '#' && preorder[i] != ',' {
i++
}
// 将当前数字记录+1
flag++
}
}
// 循环未得到结果,说明序列不全,不能成为先序序列
return false
}
提交结果