数据结构4：树

4.1 根据前序与中序序列构造二叉树

LeetCode No.105

问题描述：根据一棵树的前序遍历与中序遍历构造二叉树。

思路：根据二叉树的前序和中序（或后序和中序）的序列可唯一构造一棵二叉树，必须要有中序。前序遍历的第一个为根节点，找到根节点在中序中的位置，中序左边的节点都是根节点的左子树，右边的同理，然后可以用递归的方式求解。

示例代码：

type TreeNode struct {
  Val int
  Left *TreeNode
  Right *TreeNode
}

func index(nums []int, val int) int {
    for i, v := range nums {
        if v == val {
            return i
        }
    }
    return -1
}

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }
    if len(preorder) == 1 || len(inorder) == 1 {
        return &TreeNode{
            Val: preorder[0],
            Left: nil,
            Right: nil,
        }
    }
    val := preorder[0]
    pos := index(inorder, val)
    root := &TreeNode{
        Val: val,
        Left: buildTree(preorder[1 : pos + 1], inorder[ : pos]),
        Right: buildTree(preorder[pos + 1 : ], inorder[pos + 1:]),
    }
    return root
}