-
Notifications
You must be signed in to change notification settings - Fork 37
/
ReconstructBST.go
121 lines (102 loc) · 2.42 KB
/
ReconstructBST.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
package reconstruct_bst
// important question
import "math"
type BST struct {
Value int
Left *BST
Right *BST
}
type treeInfo struct {
rootIdx int
}
func ReconstructBst(preOrderTraversalValues []int) *BST {
treeInfo := &treeInfo{rootIdx: 0}
return reconstructBstFromRange(
math.MinInt32,
math.MaxInt32,
preOrderTraversalValues,
treeInfo,
)
}
func reconstructBstFromRange(lowerBound, upperBound int, preOrderTraversalValues []int, currentSubtreeInfo *treeInfo) *BST {
if currentSubtreeInfo.rootIdx == len(preOrderTraversalValues) {
return nil
}
rootValue := preOrderTraversalValues[currentSubtreeInfo.rootIdx]
if rootValue < lowerBound || rootValue >= upperBound {
return nil
}
currentSubtreeInfo.rootIdx += 1
leftSubtree := reconstructBstFromRange(
lowerBound,
rootValue,
preOrderTraversalValues,
currentSubtreeInfo,
)
rightSubtree := reconstructBstFromRange(
rootValue,
upperBound,
preOrderTraversalValues,
currentSubtreeInfo,
)
return &BST{Value: rootValue, Left: leftSubtree, Right: rightSubtree}
}
// 10, 4, 2, 1, 5, 17, 19, 18
// 10
// / \
// 4 17
// / \ \
// 2 5 19
// / /
// 1 18
// visit left right
// ReconstructBst1
// Why I didn't figure it out
func ReconstructBst1(preOrderTraversalValues []int) *BST {
if len(preOrderTraversalValues) == 0 {
return nil
}
currentValue := preOrderTraversalValues[0]
rightSubtreeRootIdx := len(preOrderTraversalValues)
for idx := 1; idx < len(preOrderTraversalValues); idx++ {
value := preOrderTraversalValues[idx]
if value >= currentValue {
rightSubtreeRootIdx = idx
break
}
}
leftSubtree := ReconstructBst(preOrderTraversalValues[1:rightSubtreeRootIdx])
rightSubtree := ReconstructBst(preOrderTraversalValues[rightSubtreeRootIdx:])
return &BST{
Value: currentValue,
Left: leftSubtree,
Right: rightSubtree,
}
}
// my solution
func reconstructBst(preOrderTraversalValues []int) *BST {
bst := &BST{Value: preOrderTraversalValues[0]}
for i := 1; i < len(preOrderTraversalValues); i++ {
value := preOrderTraversalValues[i]
bst.insert(value)
}
return bst
}
func (tree *BST) insert(value int) *BST {
if value < tree.Value {
if tree.Left == nil {
tree.Left = &BST {
Value: value,
}
} else {
tree.Left.insert(value)
}
} else {
if tree.Right == nil {
tree.Right = &BST{Value: value}
} else {
tree.Right.insert(value)
}
}
return tree
}