Прямой, центрированный и обратный порядок
Прямой, центрированный и обратный порядок
Одной из классических задач на структуры данных является порядок обхода вершин бинарного дерева. Существуют три стандартных вариантов обхода:
Прямой: посещается корень, левое поддерево, правое поддерево;Центрированный: посещается левое поддерево, корень, правое поддерево;Обратный: посещается левое поддерево, правое поддерево, корень;
Рассмотрим рисунок:
При прямом, центрированном и обратном обходе мы получим соответственно ABCDEF, CBAEDF и CBEFDA. В задаче требуется найти последовательность вершин при обратном обходе, если известны прямой и центрированный.
Входные данные
Первая строка содержит количество тестов c (c ≤ 2000). Каждая следующая строка является отдельным тестом и содержит количество вершин в бинарном дереве n (1 ≤ n ≤ 52) и две строки S[1] и S[2], содержащие соответственно прямой и центрированный обход дерева. Вершины дерева пронумерованы разными символами из множеств a..z и A..Z. Значения n, S[1] и S[2] разделены пробелом.
Выходные данные
Для каждого теста вывести последовательность вершин при обратном обходе дерева.
Пример
3 3 xYz Yxz 3 abc cba 6 ABCDEF CBAEDF
Yzx cba CBEFDA