通过先序和中序数组生成后序数组
给出一棵二叉树的先序和中序数组，通过这两个数组直接生成正确的后序数组。示例1
输入: [1,2,3],[2,1,3] 输出： [2,3,1]
思路：
题目意思是给出两个数组，一个是二叉树的先序遍历的数组，一个是中序遍历的数组，让求出后序数组。 考虑先序遍历中序遍历和后序遍历的规则，就可以发现，先序数组的第一位一定是root节点，而该节点在后序数组中的左边一定是左子树，节点右边一定是右子树，知道了左子树的大小，就能知道先序数组中，左子树的范围和右子树的范围，依此递归求解就行。
代码：
golang:
代码语言：javascript复制/**
*
* @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
}
