给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]提示:
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder 和 postorder 都由 不同 的值组成
- postorder 中每一个值都在 inorder 中
- inorder 保证是树的中序遍历
- postorder 保证是树的后序遍历
解题：
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(postorder) == 0 {
return nil
}
root := &TreeNode{postorder[len(postorder)-1], nil, nil}
i := 0
for ; i < len(inorder); i++ {
if inorder[i] == root.Val {
break
}
}
root.Left = buildTree(inorder[:i], postorder[:i])
root.Right = buildTree(inorder[i+1:], postorder[i:len(postorder)-1])
return root
}官方解答：
1.递归
func buildTree(inorder []int, postorder []int) *TreeNode {
idxMap := map[int]int{}
for i, v := range inorder {
idxMap[v] = i
}
var build func(int, int) *TreeNode
build = func(inorderLeft, inorderRight int) *TreeNode {
// 无剩余节点
if inorderLeft > inorderRight {
return nil
}
// 后序遍历的末尾元素即为当前子树的根节点
val := postorder[len(postorder)-1]
postorder = postorder[:len(postorder)-1]
root := &TreeNode{Val: val}
// 根据 val 在中序遍历的位置，将中序遍历划分成左右两颗子树
// 由于我们每次都从后序遍历的末尾取元素，所以要先遍历右子树再遍历左子树
inorderRootIndex := idxMap[val]
root.Right = build(inorderRootIndex+1, inorderRight)
root.Left = build(inorderLeft, inorderRootIndex-1)
return root
}
return build(0, len(inorder)-1)
}2.迭代
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(postorder) == 0 {
return nil
}
root := &TreeNode{Val: postorder[len(postorder)-1]}
stack := []*TreeNode{root}
inorderIndex := len(inorder) - 1
for i := len(postorder) - 2; i >= 0; i-- {
postorderVal := postorder[i]
node := stack[len(stack)-1]
if node.Val != inorder[inorderIndex] {
node.Right = &TreeNode{Val: postorderVal}
stack = append(stack, node.Right)
} else {
for len(stack) > 0 && stack[len(stack)-1].Val == inorder[inorderIndex] {
node = stack[len(stack)-1]
stack = stack[:len(stack)-1]
inorderIndex--
}
node.Left = &TreeNode{Val: postorderVal}
stack = append(stack, node.Left)
}
}
return root
}