根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
image.png
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 || len(inorder) == 0 {
return nil
}
rootdata := preorder[0]
root := &TreeNode{
Val: rootdata,
Left: nil,
Right: nil,
}
rootindex := getIndex(inorder, rootdata)
root.Left = buildTree(preorder[1:rootindex+1], inorder[0:rootindex])
root.Right = buildTree(preorder[rootindex+1:], inorder[rootindex+1:])
return root
}
func getIndex(array []int, val int) int {
for i := 0; i <= len(array)-1; i++ {
if array[i] == val {
return i
}
}
return -1
}
