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

知识点：

树的中序遍历和树的后序遍历

解题思路：

通过后序遍历来确定当前节点，在用后序遍历的val在中序遍历的位子来分割左右子树

语言：

Golang

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

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

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