题解 | #牛群的树形结构重建II#

知识点：

树的先序和后序遍历

解题思路：

利用先序遍历来确定当前的节点，让后再利用当前的val在中序中的位置来分割左右子树

语言：

Golang

package main
import . "nc_tools"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param preOrder int整型一维数组 
 * @param inOrder int整型一维数组 
 * @return TreeNode类
*/
func buildTreeII( preOrder []int ,  inOrder []int ) *TreeNode {
    // write code here
        index:=map[int]int{}
    for i,v:=range inOrder{
        index[v]=i
    }
     return build(inOrder,0,len(inOrder)-1,preOrder,0,len(preOrder)-1,index)

}
func build(inOrder []int,inStart,inEnd int,preOrder []int,preStart,preEnd int,index map[int]int) *TreeNode{
    if inStart>inEnd{
        return nil
    }
    rootVal:= preOrder[preStart]
    cur:=index[rootVal]
    size:=cur-inStart
    root:=&TreeNode{Val: rootVal}
    root.Left= build(inOrder,inStart,cur-1,preOrder,preStart+1,preStart+size,index)
    root.Right= build(inOrder,cur+1,inEnd,preOrder,preStart+size+1,preEnd,index)
    return root
}