Hi, here’s your problem today. This problem was recently asked by Microsoft:
You are given the preorder and inorder traversals of a binary tree in the form of arrays. Write a function that reconstructs the tree represented by these traversals.
Example: Preorder: [a, b, d, e, c, f, g] Inorder: [d, b, e, a, f, c, g]
The tree that should be constructed from these traversals is:
b c / \ /
d e f g
Here’s a start:
from collections import deque
class Node(object): def init(self, val): self.val = val self.left = None self.right = None
def str(self): q = deque() q.append(self) result = ‘’ while len(q): n = q.popleft() result += n.val if n.left: q.append(n.left) if n.right: q.append(n.right)
def reconstruct(preorder, inorder):
Fill this in.
tree = reconstruct([‘a’, ‘b’, ‘d’, ‘e’, ‘c’, ‘f’, ‘g’], [‘d’, ‘b’, ‘e’, ‘a’, ‘f’, ‘c’, ‘g’]) print tree