题解 | #重建二叉树#

利用分治法递归构造目标二叉树

/*
 * 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
    if len(pre)==0||len(vin)==0{return nil}
    //分治法
    root := TreeNode{Val: pre[0],}
    r_indx := 0
    //找出根值在中序的下标
    for i:= 0;i<len(vin);i++{
        if vin[i]==pre[0]{
            r_indx=i
            break
        }
    }
    var vin_right_val []int
    var pre_right_val []int
    
    // 找出中序序列中左子树的中序序列
    vin_left_val:=vin[:r_indx]
    // 找出前序序列中左子树的前序序列
    pre_left_val :=pre[1:1+len(vin_left_val)]
    //找右子树如果右子树存在的话
    if r_indx !=len(vin)-1{
        vin_right_val=vin[r_indx+1:]
        pre_right_val = pre[len(vin_left_val)+1:]
    }
    
    //分治构造左右子树
    left:=reConstructBinaryTree(pre_left_val,vin_left_val)
    right:=reConstructBinaryTree(pre_right_val,vin_right_val)
    
    // 归并子树
    root.Left=left
    root.Right=right
    return &root
}