eolymp
bolt
Try our new interface for solving problems
Məsələlər

Прямой, центрированный и обратный порядок

Прямой, центрированный и обратный порядок

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Одной из классических задач на структуры данных является порядок обхода вершин бинарного дерева. Существуют три стандартных вариантов обхода:

Прямой: посещается корень, левое поддерево, правое поддерево;Центрированный: посещается левое поддерево, корень, правое поддерево;Обратный: посещается левое поддерево, правое поддерево, корень;

Рассмотрим рисунок:

prb1513

При прямом, центрированном и обратном обходе мы получим соответственно ABCDEF, CBAEDF и CBEFDA. В задаче требуется найти последовательность вершин при обратном обходе, если известны прямой и центрированный.

Giriş verilənləri

Первая строка содержит количество тестов c (c2000). Каждая следующая строка является отдельным тестом и содержит количество вершин в бинарном дереве n (1n52) и две строки S[1] и S[2], содержащие соответственно прямой и центрированный обход дерева. Вершины дерева пронумерованы разными символами из множеств a..z и A..Z. Значения n, S[1] и S[2] разделены пробелом.

Çıxış verilənləri

Для каждого теста вывести последовательность вершин при обратном обходе дерева.

Nümunə

Giriş verilənləri #1
3
3 xYz Yxz
3 abc cba
6 ABCDEF CBAEDF
Çıxış verilənləri #1
Yzx
cba
CBEFDA