牛客刷题-重建二叉树（GO语言版）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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
}