题解 | #重建二叉树#

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 {
	// write code here
	if len(pre) == 0 {  return nil
	}
	root := &TreeNode{
		Val:   pre[0],
		Left:  nil,
		Right: nil,
	}
	preValIndex := getIndexInVin(vin, pre[0])    // 确定当前状态根节点元素在中序遍历中的位置
	root.Left = reConstructBinaryTree(pre[1:preValIndex+1], vin[:preValIndex])    //递归构建左子树（参数为部分切片，下同）
	root.Right = reConstructBinaryTree(pre[preValIndex+1:], vin[preValIndex+1:])  //递归构建右子树
	return root
}

func getIndexInVin(vin []int, target int) int {    // 查找target元素在vin中的索引
	for i, i2 := range vin {
		if i2 == target {
			return i
		}
	}
	return -1
}