Recca Chao 的 gitHub page

推廣網站開發,包含 Laravel 和 Kotlin 後端撰寫、自動化測試、讀書心得等。Taiwan Kotlin User Group 管理員。

View on GitHub

Hi, here's your problem today. This problem was recently asked by Amazon:

Given a binary tree, flatten the binary tree using inorder traversal. Instead of creating a new list, reuse the nodes, where the list is represented by following each right child. As such the root should always be the first element in the list so you do not need to return anything in the implementation, just rearrange the nodes such that following the right child will give us the list.

Here's an example and some starter code.

class Node: def init(self, value, left=None, right=None): self.value = value self.left = left self.right = right

def repr(self): return f"({self.value}, {self.left}, {self.right})"

def flatten_bst(root):

Fill this in.

n5 = Node(5) n4 = Node(4) n3 = Node(3, n4) n2 = Node(2, n5) n1 = Node(1, n2, n3)

1

/ \

2 3

/ /

5 4

flatten_bst(n1) print(n1)

n1 should now look like

1

\

2

\

5

\

3

\

4