트리의 중위 순회와 후위 순회가 주어졌을 때, 전위 순회를 출력하는 문제입니다. 이 문제의 힌트로 퀵소트 닮았다는 이야기를 했는데, 일단 제가 푼 방법대로면 상당히 닮았습니다. 먼저 순회의 특징부터 알아보겠습니다. postfix의 특징인 서브트리의 루트가 맨 마지막에 위치한다는 것이 있고, infix의 특징인 루트의 양쪽으로 왼쪽 서브트리와 오른쪽 서브트리가 존재하는 것이 있습니다. 다만 postfix는 왼쪽 서브트리와 오른쪽 서브트리의 경계를 알 수 없고, infix는 루트 노드가 무엇인지 알 수 없습니다. 이를 보완하기 위해 postfix로부터 루트 노드를 알아내고, 이를 이용하여 infix로부터 양쪽 서브트리를 분리합니다. 이를 재귀적으로 시행하여 트리의 구조를 생성할 수 있으며, 생성한 트리를 전위 순회 방식으로 다시 출력하면 됩니다.
실제로 infix와 prefix, 또는 infix와 postfix가 주어지면 완전한 트리를 구성할 수 있다고 합니다.
PS알못 OrbitHv의 PS