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
122
|
<<-DOC
Note: Your solution should have O(inorder.length) complexity, since this is what you will be asked to accomplish in an interview.
Let's define inorder and preorder traversals of a binary tree as follows:
Inorder traversal first visits the left subtree, then the root, then its right subtree;
Preorder traversal first visits the root, then its left subtree, then its right subtree.
For example, if tree looks like this:
1
/ \
2 3
/ / \
4 5 6
then the traversals will be as follows:
Inorder traversal: [4, 2, 1, 5, 3, 6]
Preorder traversal: [1, 2, 4, 3, 5, 6]
Given the inorder and preorder traversals of a binary tree t, but not t itself, restore t and return it.
Example
For inorder = [4, 2, 1, 5, 3, 6] and preorder = [1, 2, 4, 3, 5, 6], the output should be
restoreBinaryTree(inorder, preorder) = {
"value": 1,
"left": {
"value": 2,
"left": {
"value": 4,
"left": null,
"right": null
},
"right": null
},
"right": {
"value": 3,
"left": {
"value": 5,
"left": null,
"right": null
},
"right": {
"value": 6,
"left": null,
"right": null
}
}
}
For inorder = [2, 5] and preorder = [5, 2], the output should be
restoreBinaryTree(inorder, preorder) = {
"value": 5,
"left": {
"value": 2,
"left": null,
"right": null
},
"right": null
}
Input/Output
[time limit] 4000ms (rb)
[input] array.integer inorder
An inorder traversal of the tree. It is guaranteed that all numbers in the tree are pairwise distinct.
Guaranteed constraints:
1 ≤ inorder.length ≤ 2 · 103,
-105 ≤ inorder[i] ≤ 105.
[input] array.integer preorder
A preorder traversal of the tree.
Guaranteed constraints:
preorder.length = inorder.length,
-105 ≤ preorder[i] ≤ 105.
[output] tree.integer
The restored binary tree.
http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
DOC
describe "#restore_binary_tree" do
$preorder_index = 0
def search(items, start, end_range, target)
items[start..end_range].find_index { |x| x == target } + start
end
def build_tree(inorder, preorder, start_index, end_index)
return nil if start_index > end_index
value = preorder[$preorder_index]
node = Tree.new(value)
$preorder_index += 1
return node if start_index == end_index
index = search(inorder, start_index, end_index, value)
node.left = build_tree(inorder, preorder, start_index, index - 1)
node.right = build_tree(inorder, preorder, index + 1, end_index)
node
end
def restore_binary_tree(inorder, preorder)
build_tree(inorder, preorder, 0, inorder.size - 1).to_h
end
null = nil
[
{ inorder: [4, 2, 1, 5, 3, 6], preorder: [1, 2, 4, 3, 5, 6], x: { "value": 1, "left": { "value": 2, "left": { "value": 4, "left": null, "right": null }, "right": null }, "right": { "value": 3, "left": { "value": 5, "left": null, "right": null }, "right": { "value": 6, "left": null, "right": null } } } },
{ inorder: [2, 5], preorder: [5, 2], x: { "value": 5, "left": { "value": 2, "left": null, "right": null }, "right": null } },
{ inorder: [100], preorder: [100], x: { "value": 100, "left": null, "right": null } },
{ inorder: [-100000, -99999, -99998], preorder: [-99999, -100000, -99998], x: { "value": -99999, "left": { "value": -100000, "left": null, "right": null }, "right": { "value": -99998, "left": null, "right": null } } },
].each do |x|
it do
$preorder_index = 0
expect(restore_binary_tree(x[:inorder], x[:preorder])).to eql(x[:x])
end
end
end
|
