样例
样例1
输入:"9,3,4,#,#,1,#,#,2,#,6,#,#"
输出:true
样例2
输入:"1,#"
输出:false
样例3
输入:"9,#,#,1"
输出:false
思路
一开始想到的最坏做法是直接通过先序遍历尝试把树建起来,由于先序遍历遇到 $null$ 是会打‘#’的所以这个做法是可行的,而且复杂度是 $O(n)$。
之后观察测试例2,3,发现最后遍历到的元素一定是个叶子节点,而叶子节点后面一定是跟着连续两个‘#’的(思考先序遍历叶子节点的输出)。进一步,对于判断一个给定的先序遍历是不是二叉树,空指针,叶子结点,乃至子树结果上是等价的,都可以推出这个“子树”可以被用作其父亲节点的子节点。
有了这些想法,于是想到可以逆向遍历这个字符串,用一个栈来保存已经建立起来的子树。如果当前遇到的节点非空,那么如果栈中有两个合法的子树那就可以组合建立一个新子树(把栈中最上两个子树pop出来组合成一个新子树再push回去);如果栈中不满两个子树那么就建立不了一个合法的树就可以直接退出了。运算到最后我们应该在栈中得到有且只有一个子树。题目要求不能实事上创建树,而且前面也提到了子树的形式不重要,重要的只是当前可用的子树数量,所以也就不需要栈,用一个计数器存储数量即可。
别的细节就是把空字符串和只有一个空指针的边界情况提交给leetcode得到结果特判一下就可以了。。反正也是面向测试开发TDD。。
Golang 代码
func isValidSerialization(preorder string) bool {
if preorder == "" {
return false
} else if preorder == "#" {
return true
}
s, cnt := ","+preorder, 0
for i := len(s) - 1; i >= 0; i-- {
if s[i] != ',' { continue }
if s[i+1] == '#' { cnt++; continue }
if cnt < 2 {
return false
}
cnt = cnt - 2 + 1
}
return cnt == 1
}