51 lines
1.2 KiB
Go
51 lines
1.2 KiB
Go
package top100liked
|
|
|
|
// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked
|
|
|
|
type TreeNode struct {
|
|
Val int
|
|
Left *TreeNode
|
|
Right *TreeNode
|
|
}
|
|
|
|
// func buildTree(preorder []int, inorder []int) *TreeNode {
|
|
// if len(preorder) == 0 {
|
|
// return nil
|
|
// }
|
|
// if len(preorder) == 1 {
|
|
// return &TreeNode{Val: preorder[0]}
|
|
// }
|
|
// rootVal := preorder[0]
|
|
// root := &TreeNode{Val: rootVal}
|
|
// for i, v := range inorder {
|
|
// if v == rootVal {
|
|
// root.Left = buildTree(preorder[1:1+i], inorder[:i])
|
|
// root.Right = buildTree(preorder[1+i:], inorder[i+1:])
|
|
// break
|
|
// }
|
|
// }
|
|
// return root
|
|
// }
|
|
|
|
func buildTree(preorder, inorder []int) *TreeNode {
|
|
idx := map[int]int{}
|
|
for i, v := range inorder {
|
|
idx[v] = i
|
|
}
|
|
var dfs func(preL, preR, inL, inR int) *TreeNode
|
|
dfs = func(preL, preR, inL, inR int) *TreeNode {
|
|
if preL > preR {
|
|
return nil
|
|
}
|
|
rootVal := preorder[preL]
|
|
mid := idx[rootVal]
|
|
leftSize := mid - inL
|
|
return &TreeNode{
|
|
Val: rootVal,
|
|
Left: dfs(preL+1, preL+leftSize, inL, mid-1),
|
|
Right: dfs(preL+leftSize+1, preR, mid+1, inR),
|
|
}
|
|
}
|
|
return dfs(0, len(preorder)-1, 0, len(inorder)-1)
|
|
}
|