package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTreeByPreorderAndInorder(preorder []int, inorder []int) *TreeNode {
	// func buildTree(preorder []int, inorder []int) *TreeNode {
	nodeCnt := len(preorder)
	if nodeCnt == 0 || nodeCnt != len(inorder) {
		return nil
	}
	root := TreeNode{preorder[0], nil, nil}
	if nodeCnt == 1 { // No children
		return &root
	}
	var idx int
	for idx = 0; idx < nodeCnt && inorder[idx] != root.Val; idx++ {
		// Find the root index in inorder traversal
	}
	if idx != 0 { // If have left children
		root.Left = buildTree(preorder[1:1+idx], inorder[:idx])
	}
	if idx != nodeCnt-1 { // If have right children
		root.Right = buildTree(preorder[idx+1:], inorder[idx+1:])
	}
	return &root
}

// func main() {
// 	printTree(buildTree(
// 		[]int{1, 2, 4, 5, 3, 6, 7},
// 		[]int{4, 2, 5, 1, 6, 3, 7}))
// 	printTree(buildTree(
// 		[]int{1, 2},
// 		[]int{1, 2}))
// }