题解 | #重建二叉树#

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param pre int整型一维数组 
 * @param vin int整型一维数组 
 * @return TreeNode类
*/
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
	ma := make(map[int]int)
	for i, v := range vin {
		ma[v] = i
	}
	return dfs(pre, 0, ma, 0, len(vin)-1)
}

func dfs(pre []int, curP int, ma map[int]int, st int, en int) *TreeNode {
	if st > en || curP >= len(pre) {
		return nil
	}
	rootP := ma[pre[curP]]
	root := &TreeNode{Val: pre[curP]}
	root.Left = dfs(pre, curP+1, ma, st, rootP-1)
	root.Right = dfs(pre, curP+rootP-st+1, ma, rootP+1, en)
	return root
}