leetcode331 验证二叉树的前序序列化 golang

331. 验证二叉树的前序序列化

解题思路

对于一个合法的二叉树，其前序序列应该有以下特征 root,left,right // todo 画图

那么我们就可以先把root取出来，然后分别对left和right进行递归判断。不过这里存在一个问题，就是我们不知道left和right的长度。那么我们就在递归函数里进行判断，如果是 # 则长度为1，依次递归判断。如果是不合法的则返回-1

1. 首先把字符串按照逗号,进行切割
2. 进行递归判断
3. 如果为空，不合法
4. 如果为# 返回1
5. 否则 依次递归遍历。

代码

func isValidSerialization(preorder string) bool {
    list := strings.Split(preorder,",")
    return check(list) == len(list)
}

func check(list []string)int{
    // fmt.Println(list)
    if len(list)==0{
        return -1
    }
    if list[0] == "#"{
        return 1
    }
    left := check(list[1:])
    if left == -1{
        return -1
    }
    right := check(list[1+left:])
    if right == -1{
        return -1
    }
    return left + right + 1

}

有疑问加站长微信联系（非本文作者）