客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解法：
func reConstructBinaryTree( pre []int , vin []int ) *TreeNode {
// write code here
if len(pre) == 1{
return &TreeNode{Val:pre[0]}
}
head := TreeNode{Val:pre[0]}
idx := 0
for k := range vin{
if vin[k] == pre[0]{
idx = k
break
}
}
length := len(vin[:idx])
if idx == 0{
head.Left = nil
}else{
head.Left = reConstructBinaryTree(pre[1:length+1],vin[:idx])
}
if length + 1 < len(vin){
head.Right = reConstructBinaryTree(pre[length+1:],vin[idx+1:])
}else{
head.Right = nil
}
return &head
}
|
请发表评论