P63. 用前序和中序遍历序列构建二叉树

https://algocasts.io/episodes/M0G2DaWz

Go版本

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func build(pre []int, preStart int, preEnd int, inStart int, inPos map[int]int) *TreeNode {
    if preStart > preEnd {
        return nil
    }
    root := &TreeNode{Val: pre[preStart]}
    idx := inPos[root.Val]
    leftLen := idx - inStart

    root.Left = build(pre, preStart + 1, preStart + leftLen, inStart, inPos)
    root.Right = build(pre, preStart + leftLen + 1, preEnd, idx + 1, inPos)

    return root
}

func buildTree(pre []int, in []int) *TreeNode {
    inPos := make(map[int]int)
    for i := 0; i < len(in); i++ {
        inPos[in[i]] = i
    }
    return build(pre, 0, len(pre) - 1, 0, inPos)
}

@victorzhong

感谢 :+1:

下次发代码时,可以在头尾加上 ```,这样展示代码更好看(你的帖子我已经帮你加上了):

```go
Put your code here

```