Solve using stack

1 files changed, 60 insertions, 0 deletions

diff --git a/2020/08/21/main.rb b/2020/08/21/main.rb
new file mode 100644
index 0000000..d2d76ed
--- /dev/null
+++ b/2020/08/21/main.rb
@@ -0,0 +1,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!'