master
1<<-DOC
2Given a binary tree t and an integer s,
3determine whether there is a root to leaf path in t
4such that the sum of vertex values equals s.
5
6Example
7
8For
9
10t = {
11 "value": 4,
12 "left": {
13 "value": 1,
14 "left": {
15 "value": -2,
16 "left": null,
17 "right": {
18 "value": 3,
19 "left": null,
20 "right": null
21 }
22 },
23 "right": null
24 },
25 "right": {
26 "value": 3,
27 "left": {
28 "value": 1,
29 "left": null,
30 "right": null
31 },
32 "right": {
33 "value": 2,
34 "left": {
35 "value": -2,
36 "left": null,
37 "right": null
38 },
39 "right": {
40 "value": -3,
41 "left": null,
42 "right": null
43 }
44 }
45 }
46}
47and
48s = 7,
49the output should be hasPathWithGivenSum(t, s) = true.
50
51This is what this tree looks like:
52
53 4
54 / \
55 1 3
56 / / \
57 -2 1 2
58 \ / \
59 3 -2 -3
60Path 4 -> 3 -> 2 -> -2 gives us 7, the required sum.
61
62For
63
64t = {
65 "value": 4,
66 "left": {
67 "value": 1,
68 "left": {
69 "value": -2,
70 "left": null,
71 "right": {
72 "value": 3,
73 "left": null,
74 "right": null
75 }
76 },
77 "right": null
78 },
79 "right": {
80 "value": 3,
81 "left": {
82 "value": 1,
83 "left": null,
84 "right": null
85 },
86 "right": {
87 "value": 2,
88 "left": {
89 "value": -4,
90 "left": null,
91 "right": null
92 },
93 "right": {
94 "value": -3,
95 "left": null,
96 "right": null
97 }
98 }
99 }
100}
101and
102s = 7,
103the output should be hasPathWithGivenSum(t, s) = false.
104
105This is what this tree looks like:
106
107 4
108 / \
109 1 3
110 / / \
111 -2 1 2
112 \ / \
113 3 -4 -3
114There is no path from root to leaf with the given sum 7.
115
116Input/Output
117
118[time limit] 4000ms (rb)
119[input] tree.integer t
120
121A binary tree of integers.
122
123Guaranteed constraints:
1240 ≤ tree size ≤ 5 · 104,
125-1000 ≤ node value ≤ 1000.
126
127[input] integer s
128
129An integer.
130
131Guaranteed constraints:
132-4000 ≤ s ≤ 4000.
133
134[output] boolean
135
136Return true if there is a path from root to leaf in t such that the sum of node values in it is equal to s,
137otherwise return false.
138DOC
139
140describe "#path_with_given_sum?" do
141 def leaf?(node)
142 node.left.nil? && node.right.nil?
143 end
144
145 def path_with_given_sum?(tree, target_sum)
146 stack = []
147 stack.push(tree) if tree
148 sum = 0
149 until stack.empty?
150 node = stack.pop
151 sum += node.value
152 return true if leaf?(node) && sum == target_sum
153
154 stack.push(node.left) if node.left
155 stack.push(node.right) if node.right
156 end
157 sum == target_sum
158 end
159
160 def path_with_given_sum?(tree, target)
161 return target.zero? if tree.nil?
162 new_target = target - tree.value
163 return new_target.zero? if leaf?(tree)
164 return true if tree.left && path_with_given_sum?(tree.left, new_target)
165 return true if tree.right && path_with_given_sum?(tree.right, new_target)
166 false
167 end
168
169 def path_with_given_sum?(tree, target)
170 return target.zero? if tree.nil?
171 new_target = target - tree.value
172 path_with_given_sum?(tree.left, new_target) || path_with_given_sum?(tree.right, new_target)
173 end
174
175 [
176 { t: { "value": 4, "left": { "value": 1, "left": { "value": -2, "left": nil, "right": { "value": 3, "left": nil, "right": nil } }, "right": nil }, "right": { "value": 3, "left": { "value": 1, "left": nil, "right": nil }, "right": { "value": 2, "left": { "value": -2, "left": nil, "right": nil }, "right": { "value": -3, "left": nil, "right": nil } } } }, s: 7, x: true },
177 { t: { "value": 4, "left": { "value": 1, "left": { "value": -2, "left": nil, "right": { "value": 3, "left": nil, "right": nil } }, "right": nil }, "right": { "value": 3, "left": { "value": 1, "left": nil, "right": nil }, "right": { "value": 2, "left": { "value": -4, "left": nil, "right": nil }, "right": { "value": -3, "left": nil, "right": nil } } } }, s: 7, x: false },
178 { t: { "value": 4, "left": { "value": 1, "left": { "value": -2, "left": nil, "right": { "value": 3, "left": nil, "right": nil } }, "right": nil }, "right": { "value": 3, "left": { "value": 1, "left": { value: -1, left: nil, right: nil}, "right": nil }, "right": { "value": 2, "left": { "value": -4, "left": nil, "right": nil }, "right": { "value": -3, "left": nil, "right": nil } } } }, s: 7, x: true },
179 { t: nil, s: 0, x: true },
180 { t: nil, s: 1, x: false },
181 { t: { "value": 5, "left": nil, "right": nil }, s: 5, x: true },
182 { t: { "value": 5, "left": nil, "right": nil }, s: -5, x: false },
183 { t: { "value": 5, "left": nil, "right": nil }, s: 0, x: false },
184 { t: { "value": 8, "left": nil, "right": { "value": 3, "left": nil, "right": nil } }, s: 8, x: false },
185 ].each do |x|
186 it do
187 expect(path_with_given_sum?(Tree.build_from(x[:t]), x[:s])).to eql(x[:x])
188 end
189 end
190
191 class Tree
192 attr_accessor :value, :left, :right
193
194 def initialize(value, left: nil, right: nil)
195 @value = value
196 @left = left
197 @right = right
198 end
199
200 def to_h
201 { value: value, left: left&.to_h, right: right&.to_h }
202 end
203
204 def self.build_from(hash)
205 return nil if hash.nil?
206 Tree.new(hash[:value], left: build_from(hash[:left]), right: build_from(hash[:right]))
207 end
208 end
209end