题解 | #重建二叉树#
重建二叉树
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
return build(pre, vin)
}
func build(pre []int, vin []int) *TreeNode {
if len(pre) == 0 {
return nil
}
root := &TreeNode{Val: pre[0]}
position := findPosition(pre[0], vin)
root.Left = build(pre[1:position + 1], vin[:position])
root.Right = build(pre[position+1:], vin[position + 1:])
return root
}
func findPosition(target int, arr []int) int {
for index, val := range arr {
if val == target {
return index
}
}
return -1
}
