func serialByPre(head *Node) string {
    // base case
    if head == nil {
        return "#_"
    }
    str := strconv.Itoa(head.value) + "_"
    str += serialByPre(head.left)
    str += serialByPre(head.right)
    return str
}

func reconPreOrder(queue *[]string) *Node {
    cur := (*queue)[0]
    *queue = (*queue)[1:]
    // base case
    if cur == "#" {
        return nil
    }
    val, _ := strconv.Atoi(cur)
    head := &Node{value: val}
    head.left = reconPreOrder(queue)
    head.right = reconPreOrder(queue)
    return head
}

func reconByPreString(str string) *Node {
    if len(str) == 0 {
        return nil
    }
    chars := strings.Split(str, "_")
    return reconPreOrder(&chars)
}

func serialByLevel(head *Node) string {
    // base case
    if head == nil {
        return "#_"
    }
    queue := make([]*Node, 0, 32)
    res := strconv.Itoa(head.value) + "_"
    queue = append(queue, head)
    for len(queue) != 0 {
        head = queue[0]
        queue = queue[1:]
        if head.left != nil {
            res += strconv.Itoa(head.left.value) + "_"
            queue = append(queue, head.left)
        } else {
            res += "#_"
        }
        if head.right != nil {
            res += strconv.Itoa(head.right.value) + "_"
            queue = append(queue, head.right)
        } else {
            res += "#_"
        }
    }
    return res
}

func generateNodeByString(val string) *Node {
    if val == "#" {
        return nil
    }
    value, _ := strconv.Atoi(val)
    return &Node{value: value}
}
func reconByLevelString(levelStr string) *Node {
    values := strings.Split(levelStr, "_")
    index := 0
    head := generateNodeByString(values[0])
    index++
    queue := make([]*Node, 0, 32)
    if head != nil {
        queue = append(queue, head)
    }
    var node *Node
    for len(queue) != 0 {
        node = queue[0]
        queue = queue[1:]
        node.left = generateNodeByString(values[index])
        index++
        node.right = generateNodeByString(values[index])
        index++
        if node.left != nil {
            queue = append(queue, node.left)
        }
        if node.right != nil {
            queue = append(queue, node.right)
        }
    }
    return head
}