题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
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
}
