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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
description = <<-DESC
Given a binary tree and a number k, your task is to find the sum of tree nodes at level k.
The binary tree is represented by a string tree with the format: (<node-value>(<left subtree>)(<right subtree>)).
Example
For tree = "(0(5(6()())(14()(9()())))(7(1()())(23()())))" and k = 2, the output should be
treeLevelSum(tree, k) = 44.
Explanation: The nodes at level 2 are 6, 14, 1, and 23, so the answer is 6 + 14 + 1 + 23 = 44.
Input/Output
[time limit] 4000ms (rb)
[input] string tree
A valid string representing a tree.
Guaranteed constraints:
2 ≤ tree.length ≤ 105.
All the values in a given tree are guaranteed to be integers.
[input] integer k
Guaranteed constraints:
0 ≤ k ≤ 105.
[output] integer
The total sum of all the values at level k in a tree.
https://en.wikipedia.org/wiki/S-expression
DESC
describe "tree_level_sum" do
# parse s-expression
def parse(tokens, values, offset = 0)
struct = []
while offset < tokens.length
if "(" == tokens[offset]
offset, items = parse(tokens, values, offset + 1)
struct << items
elsif ")" == tokens[offset]
break
else
struct << values.shift
end
offset += 1
end
return [offset, struct]
end
def build_tree(string)
tokens = string.gsub("(", " ( ").gsub(")", " ) ").split(" ")
values = string.scan(/\d+/).map(&:to_i)
_, tree = parse(tokens, values, 0)
tree[0]
end
def tree_level_sum(tree, target)
tree = build_tree(tree)
queue = [node: tree, level: 0]
sum = 0
until queue.empty?
top = queue.shift
if top[:level] == target
sum += top[:node][0]
end
left = top[:node][1]
right = top[:node][2]
if left.size > 0
queue.push(node: left, level: top[:level] + 1)
end
if right.size > 0
queue.push(node: right, level: top[:level] + 1)
end
end
sum
end
def tree_level_sum(tree, target)
# ( + level
# ) - level
# if level == target
# add number to sum
level = -1
sum = 0
tokens = tree.gsub("(", " ( ").gsub(")", " ) ").split(" ")
tokens.each do |token|
if token == "("
level += 1
elsif token == ")"
level -= 1
elsif level == target
sum += token.to_i
end
end
sum
end
<<-EXAMPLE
0
/ \
/ \
5 7
/ \ / \
6 14 1 23
\
9
(0(5(6()())(14()(9()()))) (7(1()())(23()())))
[0,
[ 5,
[6, [], [] ],
[14, [], [9, [], []]]
],
[ 7,
[1, [], []],
[23, [], []]
]
]
level 2: tree[1][1][0] + tree[1][2][0] + tree[2][1][0] + tree[2][2][0] = 44
EXAMPLE
[
{tree: "(0(5(6()())(14()(9()())))(7(1()())(23()())))", k: 2, expected: 44},
{tree: "(3(3()())(1()()))", k: 1, expected: 4},
{tree: "(0(5(6()())(4()(9()())))(7(1()())(3()())))", k: 2, expected: 14},
{tree: "(3()())", k: 0, expected: 3},
{tree: "(0(5()())())", k: 1, expected: 5},
].each do |x|
it do
expect(tree_level_sum(x[:tree], x[:k])).to eql(x[:expected])
end
end
end
|
