4.1 根据前序与中序序列构造二叉树
问题描述：根据一棵树的前序遍历与中序遍历构造二叉树。
思路：根据二叉树的前序和中序（或后序和中序）的序列可唯一构造一棵二叉树，必须要有中序。前序遍历的第一个为根节点，找到根节点在中序中的位置，中序左边的节点都是根节点的左子树，右边的同理，然后可以用递归的方式求解。
示例代码：
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
}