题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
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, 0, len(pre) - 1, vin, 0, len(vin) - 1)
}
//构造包含边界输入的辅助函数，真香！！！
func build(pre []int, preS, preE int, vin []int, vinS, vinE int) *TreeNode {
if preS > preE {return nil}
rootValue := pre[preS]
index := 0
for i := vinS; i <= vinE; i++ {
if vin[i] == rootValue {
index = i
break
}
}
root := &TreeNode{Val:rootValue}
leftSize := index - vinS
root.Left = build(pre, preS+1, preS + leftSize, vin, vinS, index-1)
root.Right = build(pre, preS+1+leftSize, preE, vin, index+1, vinE)
return root
}
