【二叉树算法】golang
/ 通过中序遍历和后序遍历数组构造二叉树
func buildBinaryTree(inorder, postorder []int) *TreeNode {
// 终止
if postorder == nil {
return &TreeNode{}
}
// 从后序遍历拿到根节点
rootVal := postorder[len(postorder)-1]
root := &TreeNode{Val: rootVal}
if len(postorder) == 1 {
return root
}
// 分割左右子树
var indexInorder int
for i := 0; i < len(inorder); i++ {
if inorder[i] == rootVal {
indexInorder = i
}
}
// 切割，左闭右开
inLeft, inRight := inorder[:indexInorder], inorder[indexInorder+1:]
postLeft, postRight := postorder[:len(inLeft)], postorder[len(inLeft):len(postorder)-1]
root.Left = buildBinaryTree(inLeft, postLeft)
root.Right = buildBinaryTree(inRight, postRight)
return root
}