package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
	nodeCnt := len(inorder)
	if nodeCnt == 0 || nodeCnt != len(postorder) {
		return nil
	}
	root := TreeNode{postorder[nodeCnt-1], nil, nil}
	if nodeCnt == 1 {
		return &root
	}
	var idx int
	for idx = 0; idx < nodeCnt && inorder[idx] != root.Val; idx++ {
	}
	if idx != 0 {
		root.Left = buildTree(inorder[:idx], postorder[:idx])
	}
	if idx != nodeCnt-1 {
		root.Right = buildTree(inorder[idx+1:], postorder[idx:nodeCnt-1])
	}
	return &root
}

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