题解 | #重建二叉树#

package main

/*
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
*/

func reConstructBinaryTree( pre []int ,  vin []int ) *TreeNode {
    var i int
    length := len(pre)
    if length == 0 {
        return nil
    }
    root := &TreeNode{pre[0], nil, nil} //根据前序遍历的第一个节点创建根节点
    for i = 0; i < length; i ++ {
        if vin[i] == pre[0] { //找出在中序遍历中根节点的位置
            break
        }
    }
    root.Left = reConstructBinaryTree(pre[1:len(vin[:i])+1], vin[:i]) //左子树的前序遍历和中序遍历
    root.Right = reConstructBinaryTree(pre[len(vin[:i])+1:], vin[i+1:]) //右子树的前序遍历和中序遍历
    return root
}