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)
}