从前序与中序遍历构造二叉树
一句话说明
前序第一个元素一定是根，中序能把左右子树一刀切开。
Go 代码
func buildTree(preorder []int, inorder []int) *TreeNode {
pos := make(map[int]int)
for i, v := range inorder {
pos[v] = i
}
var build func(pl, pr, il, ir int) *TreeNode
build = func(pl, pr, il, ir int) *TreeNode {
if pl > pr {
return nil
}
rootVal := preorder[pl]
mid := pos[rootVal]
leftSize := mid - il
root := &TreeNode{Val: rootVal}
root.Left = build(pl+1, pl+leftSize, il, mid-1)
root.Right = build(pl+leftSize+1, pr, mid+1, ir)
return root
}
return build(0, len(preorder)-1, 0, len(inorder)-1)
}关键点
前序负责定根，中序负责切区间，哈希表负责把找根的位置从 O(n) 降到 O(1)。