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
|
def assert_equals(x, y)
raise [x, y].inspect unless x == y
end
class Node
attr_accessor :left, :right, :value
def initialize(value)
@value = value
end
end
class Solution
def self.run(tree, level = 0)
return unless tree
return tree if bst?(tree, -100, 100)
left = run(tree.left, level + 1)
right = run(tree.right, level + 1)
if left && right
left_size = size(left)
right_size = size(right);
left_size > right_size ? tree.left : tree.right
else
tree.left || tree.right
end
end
def self.size(tree, s = 0)
return s if tree.nil?
size(tree.left, s) + size(tree.right, s) + 1
end
def self.bst?(tree, min, max)
return true if tree.nil?
return if tree.left && tree.left.value > min
return if tree.right && tree.right.value < max
bst?(tree.left, min, tree.value) && bst?(tree.right, tree.value, max)
end
end
node = Node.new(5)
node.left = Node.new(6)
node.right = Node.new(7)
node.left.left = Node.new(2)
node.right.left = Node.new(4)
node.right.right = Node.new(9)
assert_equals(Solution.run(node)&.value, node.right&.value)
puts "YAY!"
|
