leetcode331 验证二叉树的前序序列化 golang-木庄网络博客

本文摘自网络，作者，侵删。

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

解题思路

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

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

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

代码

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

}

本文来自：简书

感谢作者：lucasgao

查看原文：leetcode331 验证二叉树的前序序列化 golang

相关阅读 >>

Golang的Gormt和组合实战

Golang环境的安装

关于Golang gc 垃圾回收机制的详解

protoc 插件编写之一 (protoc 插件的原理)