-
Notifications
You must be signed in to change notification settings - Fork 32
/
problem.go
32 lines (29 loc) · 836 Bytes
/
problem.go
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
package day48
// BinaryTree is a binary tree with rune values.
type BinaryTree struct {
value string
left, right *BinaryTree
}
// Reconstruct takes a pre-order and in-order string representation
// and then returns a BinaryTree that conforms to both of those representations.
func Reconstruct(preorder, inorder []string) (*BinaryTree, []string) {
node := &BinaryTree{preorder[0], nil, nil}
preorder = preorder[1:]
if len(inorder) == 1 {
return node, preorder
}
index := search(inorder, node.value)
node.left, preorder = Reconstruct(preorder, inorder[:index])
node.right, preorder = Reconstruct(preorder, inorder[index+1:])
return node, preorder
}
func search(strs []string, target string) int {
var result int
for index, str := range strs {
if str == target {
result = index
break
}
}
return result
}