从中序与后序遍历构造二叉树
一句话说明
后序最后一个元素是根，中序仍然负责切左右子树。
Go 代码
func buildTree(inorder []int, postorder []int) *TreeNode {
pos := make(map[int]int)
for i, v := range inorder {
pos[v] = i
}
var build func(il, ir, pl, pr int) *TreeNode
build = func(il, ir, pl, pr int) *TreeNode {
if il > ir {
return nil
}
rootVal := postorder[pr]
mid := pos[rootVal]
leftSize := mid - il
root := &TreeNode{Val: rootVal}
root.Left = build(il, mid-1, pl, pl+leftSize-1)
root.Right = build(mid+1, ir, pl+leftSize, pr-1)
return root
}
return build(0, len(inorder)-1, 0, len(postorder)-1)
}