题解 | #重建二叉树#

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 {
	if len(pre) == 0 {
		return nil
	}
	root := &TreeNode{Val: pre[0]}
	pos := findPos(vin, pre[0])
	root.Left = reConstructBinaryTree(pre[1:len(pre[:pos])+1], vin[:pos])
	root.Right = reConstructBinaryTree(pre[len(pre[:pos])+1:], vin[pos+1:])
	return root
}

func findPos(arr []int, num int) int {
	for index, val := range arr {
		if val == num {
			return index
		}
	}
	return -1
}