2021-08-01：如果只给定一个二叉树前序遍历数组pre和中序遍历数
2021-08-01：如果只给定一个二叉树前序遍历数组pre和中序遍历数组in，能否不重建树，而直接生成这个二叉树的后序数组并返回。已知二叉树中没有重复值。
福大大答案2021-08-01：
先序遍历：根左右。
中序遍历：左根右。
先序遍历找到【根】，在中序找到【根】的位置，计算出【左】长度和【右】长度。放在后序遍历相应位置。最后递归。
代码用golang编写。代码如下：
packagemainimport“fmt”funcmain(){pre:=[]int{1,2,3}in:=[]int{2,1,3}ret:=preInToPos2(pre,in)fmt.Println(ret)}funcpreInToPos2(pre[]int,in[]int)[]int{ifpre==nil||in==nil||len(pre)!=len(in){returnnil}N:=len(pre)inMap:=make(map[int]int)fori:=0;i<N;i++{inMap[in[i]]=i}pos:=make([]int,N)process2(pre,0,N-1,in,0,N-1,pos,0,N-1,inMap)returnpos}funcprocess2(pre[]int,L1int,R1int,in[]int,L2int,R2int,pos[]int,L3int,R3int,inMapmap[int]int){ifL1>R1{return}ifL1==R1{pos[L3]=pre[L1]return}pos[R3]=pre[L1]mid:=inMap[pre[L1]]leftSize:=mid-L2process2(pre,L1+1,L1+leftSize,in,L2,mid-1,pos,L3,L3+leftSize-1,inMap)process2(pre,L1+leftSize+1,R1,in,mid+1,R2,pos,L3+leftSize,R3-1,inMap)}
执行结果如下：
***
