105. 从前序与中序遍历序列构造二叉树

难度: 中等




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func buildTree(preorder []int, inorder []int) *TreeNode {

var root *TreeNode

if len(preorder) < 1 || len(inorder) < 1{
return root
}

left := find(inorder,preorder[0])

if left < 0{
return root
}

root = &TreeNode{
Val:preorder[0],
Left:buildTree(preorder[1:left+1],inorder[0:left]),
Right:buildTree(preorder[left+1:],inorder[left+1:]),
}
return root
}


func find(inorder []int,target int) int {


for i := 0; i < len(inorder);i++ {

if target == inorder[i] {
return i
}
}

return -1
}