// 中序遍历转字符串
func (this *Codec) serialize10(root *TreeNode) string {
    var str string

    // 定义一个匿名函数,用作递归遍历
    var dfs func(node *TreeNode)
    dfs = func(root *TreeNode) {
        // 当递归到某个节点的最后,当做null返回
        if root == nil {
            str += "null,"
            return
        }
        // 中序遍历,先遍历 父节点,再遍历 左 和 右 子节点
        str += strconv.Itoa(root.Val) + ","
        dfs(root.Left)
        dfs(root.Right)
    }
    // 执行递归遍历操作
    dfs(root)

    // 最后可能得出结果,比如 "-1,-2,-3,null,-5,0,1,null,null,null,null"
    // 所以需要处理掉后面的 无效的 null 即可
    // 操作方法很简单, 倒序遍历,遇到正常的数 就返回
    arr := strings.Split(str, ",")
    for i := len(arr) - 1; i >= 0; i-- {
        if arr[i] != "null" && arr[i] != "" {
            break
        }
        arr = arr[:i]
    }
    // 最后重新拼凑成字符串返回即可
    return strings.Join(arr, ",")
}

// 中序遍历转二叉树
func (this *Codec) deserialize10(data string) *TreeNode {
    // 先把字符串进行按照逗号分割,成一个字符串数组
    sp := strings.Split(data, ",")
    // 定义一个匿名函数做递归操作
    var build func() *TreeNode

    build = func() *TreeNode {
        // 当数组为空,则递归结束,就返回出去
        if len(sp) == 0 {
            return nil
        }
        // 如果数组元素为 null, 说明它肯定没有子节点了,右移一位,然后返回
        if sp[0] == "null" {
            sp = sp[1:]
            return nil
        }
        // 中序遍历赋值
        val, _ := strconv.Atoi(sp[0])
        // 字符串数组右移一位
        sp = sp[1:]
        // 然后进行 中序遍历,先递归左节点
        return &TreeNode{
            Val:   val,
            Left:  build(),
            Right: build(),
        }
    }
    return build()
}

// 层序遍历二叉树
func (this *Codec) serialize(root *TreeNode) string {

    if root == nil {
        return ""
    }

    var str string
    // 先把第一层放入到队列里, 正常就一个根节点
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        // 遍历某层的时候,定义一个 临时的队列,当本层队列遍历完成后, 用临时的队列替换原有的队列,达到不断遍历不同楼层的队列
        var queueTemp []*TreeNode
        // 此变量是为了去除叶子节点无效的 null,比如最后一层都是null, 那么这层其实是可以不要的
        var hasNext bool
        // 依次循环队列
        for i := 0; i < len(queue); i++ {
            var iStr string
            // 如果这个队列的这个值为空,那么用 null 代替这个值
            if queue[i] == nil {
                if !hasNext && i == len(queue)-1 {
                    break
                }
                str += "null,"
                continue
            }
            iStr = strconv.Itoa(queue[i].Val)
            // 正常的值 转成字符串,然后进行拼接
            str += iStr + ","
            // 当队列的左子节点不为空,那么下一层的队列元素+1,另外,说明下一层有正常的值
            if queue[i].Left != nil {
                hasNext = true
            }
            queueTemp = append(queueTemp, queue[i].Left)

            if queue[i].Right != nil {
                hasNext = true
            }
            queueTemp = append(queueTemp, queue[i].Right)
        }
        // 如果有下一层,就用新生成的队列替换原有的队列,然后再次遍历下一层
        if hasNext {
            queue = queueTemp
        } else {
            break
        }
    }
    // 最后去除掉最后一个 逗号, 返回正常结果
    str = strings.TrimRight(str, ",")
    return str
}

// 层序遍历转字符串
func (this *Codec) deserialize(data string) *TreeNode {
    if len(data) == 0 {
        return nil
    }

    // 先将字符串按照 逗号 进行切割,分成一个字符串数组
    arr := strings.Split(data, ",")
    // 定义一个 map, key是每层, value是 该层的 队列
    levelMap := make(map[int][]*TreeNode)
    // 初始化层, 当前层从0开始
    var level int
    val, _ := strconv.Atoi(arr[0])
    // 第一层第一个元素就是 根节点, 放到 第一层的队列里
    levelMap[level] = []*TreeNode{{Val: val}}
    // 此时层到1层了
    level++

    // 定一个两个标记位
    // up表示 当前队列遍历的 指针位置(下标)
    // lr 表示 当前遍历到是左节点还是有节点
    // 比如 队列[1,2,3], 当up = 0的时候, 队列的值为1, 然后lr为0,表示当前在 1 的左子节点, 当 lr = 1 表示 当前在1的右子节点
    var up, lr int
    // 遍历所有元素
    for i, v := range arr {
        // 第一个元素就是根节点,已经在上面写了,直接跳过
        if i == 0 {
            continue
        }

        var temp *TreeNode
        // 如果 值为 null, 说明该节点为 nil
        // 否则 该节点的值就是 转成字符串的值
        if v == "null" {
            temp = nil
        } else {
            val, _ = strconv.Atoi(v)
            temp = &TreeNode{Val: val}
            // 把该节点 放到该层的队列里
            levelMap[level] = append(levelMap[level], temp)
        }

        // 该循环 是把这个 节点 赋给上层某个节点,这时候就需要找 应该在哪个节点
        //       1
        //     /  \
        //    2    3
        //   / \  / \
        //  4  5  6  7
        // 比如我们现在是2节点, 看上层现在已经遍历到队列里哪个节点哪个节点了,比如up= 0, lr = 0 说明 2应该放到 1的节点下, 且为它的左节点
        for {
            // 这层如果节点已经遍历到了最后, 那么说明该楼层已经遍历完了,那么就应该跳到下一层,然后 这些数值就恢复到初始化
            if len(levelMap[level-1]) <= up {
                level++
                up = 0
                lr = 0
            }

            // lr 为左节点, 赋值给上一层的左节点,并将 标志位lr改成右节点
            if lr == 0 {
                levelMap[level-1][up].Left = temp
                lr = 1
            } else {
                // lr为右节点, 那么 队列下标可以右移一位, 并把标志位 lr 重置成左节点
                levelMap[level-1][up].Right = temp
                up++
                lr = 0
            }
            break
        }
        // 如果该楼层节点遍历完成,就跳到下一层,并重置标记位
        if len(levelMap[level-1]) <= up {
            level++
            up = 0
            lr = 0
        }

    }
    return levelMap[0][0]
}