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
|
def assert_equal(x, y)
raise [x, y].inspect unless x == y
end
class Node
attr_accessor :left, :right, :value
def initialize(value)
@value = value
end
def preorder
[value, self.left&.preorder, self.right&.preorder].flatten.compact
end
end
class Solution
# time: O(logn)
# space: O(n)
def self.run(node)
stack = []
stack.push(node)
until stack.empty?
item = stack.pop
tmp = item.left
item.left = item.right
item.right = tmp
stack.push(item.left) if item.left
stack.push(item.right) if item.right
end
end
end
=begin
a
/ \
b c
/ \ /
d e f
a
/ \
c b
/ / \
f d e
=end
root = Node.new('a')
root.left = Node.new('b')
root.right = Node.new('c')
root.left.left = Node.new('d')
root.left.right = Node.new('e')
root.right.left = Node.new('f')
assert_equal(root.preorder, ['a', 'b', 'd', 'e', 'c', 'f'])
Solution.run(root)
assert_equal(root.preorder, ['a', 'c', 'f', 'b', 'e', 'd'])
puts 'Yay!'
|
