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

给出一棵二叉树的先序和中序数组，通过这两个数组直接生成正确的后序数组。示例1

输入:
[1,2,3],[2,1,3]
输出：
[2,3,1]

思路：

题目意思是给出两个数组，一个是二叉树的先序遍历的数组，一个是中序遍历的数组，让求出后序数组。
考虑先序遍历中序遍历和后序遍历的规则，就可以发现，先序数组的第一位一定是root节点，而该节点在后序数组中的左边一定是左子树，节点右边一定是右子树，知道了左子树的大小，就能知道先序数组中，左子树的范围和右子树的范围，依此递归求解就行。

代码：

golang:

/**
 *
 * @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
}