算法训练营day33(补)，复习二叉树1
// 889. 根据前序和后序遍历构造二叉树
// 前序中左右 后序遍历左右中
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}
root := &TreeNode{}
root.Val = preorder[0]
//前序数组去掉root节点
preorder = preorder[1:]
//后序数组去掉root节点
postorder = postorder[:len(postorder)-1]
//如果前序数组只剩1个，说明只有左子树或者右子树
if len(postorder) == 1 {
root.Left = &TreeNode{Val: postorder[0]}
return root
}
index := 0
for ; index < len(postorder); index++ {
if postorder[index] == preorder[0] {
break
}
}
if len(postorder) > 1 {
leftPostorder := postorder[:index+1]
rightPostorder := postorder[index+1:]
leftPreorder := preorder[:index+1]
rightPreorder := preorder[index+1:]
root.Left = constructFromPrePost(leftPreorder, leftPostorder)
root.Right = constructFromPrePost(rightPreorder, rightPostorder)
}
return root
}