通过先序和中序数组生成后序数组

/**
 *
 * @param preOrder int整型一维数组 the array1
 * @param inOrder int整型一维数组 the array2
 * @return int整型一维数组
 */
// [1,2,3],[2,1,3]
func findOrder( preOrder []int ,  inOrder []int ) []int {
    if len(preOrder) == 0 || len(inOrder) == 0 {
    	return nil
    }

    // 保存中序数组的下标，加速查找根节点在中序数组中的位置
    indexMap := make(map[int]int, len(inOrder))
    for i, num := range inOrder {
    	indexMap[num] = i
    }

    var res = make([]int, 0)
    genPastOrder(preOrder, 0, len(preOrder) - 1, inOrder, 0, len(inOrder) - 1, indexMap, &res)
    for i,j := 0, len(res)-1; i < j; {
    	res[i], res[j] = res[j], res[i]
    	i++
    	j--
    }
    return res
}

func genPastOrder(preOrder []int, i, j int, inOrder []int, k, l int, indexMap map[int]int, res *[]int) {
    if i > j || k > l || len(*res) == len(preOrder) {
    	return
    }
    // 前序数组的第一个节点一定是根节点
    root := preOrder[i]
    *res = append(*res, root)

    //找到根节点在右子树中的位置
    index := indexMap[root]

    // 右子树
    genPastOrder(preOrder, i + (index - k) + 1, j, inOrder, index+1, l, indexMap, res)
    // 左子树
    genPastOrder(preOrder, i+1, i + (index - k), inOrder, k, index-1, indexMap, res)
    return
}