CT021

Reconstruct the Ancestor Tree

HardAcceptance: 0.0%

The Codetikki historians found two traversal records of an ancient family tree: a pre-order and an in-order listing. They want to reconstruct the original tree. Given pre-order and in-order traversals of a binary tree, reconstruct the tree and output its post-order traversal as space-separated values. Input: first line n, second line n pre-order values, third line n in-order values. Output: post-order traversal.

Example 1:

Input: 7 a b d e c f g d b e a f c g

Output: d e b f g c a

Example 2:

Input: 3 a b c b a c

Output: b c a

Constraints:

1 <= n <= 10^4 All values are distinct single lowercase letters

Tags:

trees recursion divide-and-conquer

Test Cases:No test cases

No test cases available.