leetcode-go/medium/331.verify-preorder-serialization-of-a-binary-tree.go

func isValidSerialization(preorder string) bool {
	tree := strings.Split(preorder, ",")
	n := len(tree)
	if n == 0 || (n == 1 && tree[0] != "#") || (tree[0] == "#" && 1 < n) {
		return false
	}
	st := []int{-1} // 0 for left, and 1 for right
	l, i, next := 1, 1, 0
	for ; i < n && l != 0; i++ {
		if next == 0 {
			st = append(st, 0)
			l++
			if tree[i] == "#" {
				next = 1
			}
		} else {
			if tree[i] == "#" {
				l--
				st = st[:l]
				for 2 < l && st[l-1] == 1 {
					l--
					if st[l-1] != 0 {
						return false
					}
					l--
					st = st[:l]
				}
			} else {
				st = append(st, 1)
				l++
				next = 0
			}
		}
	}
	return len(st) == 1 && i == n
}