이 문제에서는 이진 트리의 중위 순회(inorder)와 후위 순회(postorder) 결과가 주어지며, 우리의 목표는 해당 트리의 전위 순회(preorder) 결과를 출력하는 것입니다.
먼저 예시를 통해 문제를 살펴보겠습니다.
Input: inorder: 16 7 21 12 1 5 9 postorder: 16 21 7 1 9 5 12 Output: preorder: 12 7 16 21 5 1 9
위 입력값에 대응하는 이진 트리는 다음과 같습니다.
문제 해결 접근 방법
가장 단순한 방법은 주어진 두 순회 결과로 트리를 직접 생성한 뒤, 완성된 트리를 다시 전위 순회하는 것입니다. 하지만 이 방식은 트리를 실제로 구성해야 하므로 구현이 복잡하고 시스템에도 큰 부담을 줍니다.
보다 효율적인 해결책은 스택(stack) 자료구조를 활용하는 것입니다. 핵심 아이디어는 다음과 같습니다.
- 후위 순회의 마지막 원소가 곧 트리의 루트(root)입니다.
- 중위 순회에서 루트를 기준으로, 루트보다 앞에 있는 원소들은 모두 왼쪽 서브트리에, 뒤에 있는 원소들은 오른쪽 서브트리에 속합니다.
- 루트를 찾으면 오른쪽 서브트리 → 왼쪽 서브트리 순서로 재귀적으로 탐색하면서 각 노드의 값을 스택에 저장(push)합니다.
- 모든 탐색이 끝난 뒤 스택에서 원소를 하나씩 꺼내면(pop), 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 순서인 전위 순회 결과를 얻을 수 있습니다.
이렇게 하면 트리를 실제로 만들지 않고도 주어진 순회 정보만으로 전위 순회를 빠르게 계산할 수 있습니다.
자바(Java) 구현 예제
import java.util.Stack;
public class Main {
static int postIndex;
void preOrder(int[] in, int[] post, int inStrt, int inEnd, Stack<Integer> preorder) {
if (inStrt > inEnd)
return;
int val = post[postIndex];
int inIndex = searchValue(in, val);
postIndex--;
preOrder(in, post, inIndex + 1, inEnd, preorder);
preOrder(in, post, inStrt, inIndex - 1, preorder);
preorder.push(val);
}
void printPreOrderTraversal(int[] in, int[] post) {
int len = in.length;
postIndex = len - 1;
Stack<Integer> preorder = new Stack<Integer>();
preOrder(in, post, 0, len - 1, preorder);
while (preorder.empty() == false)
System.out.print(preorder.pop() + " ");
}
int searchValue(int[] in, int data) {
int i = 0;
for (i = 0; i < in.length; i++)
if (in[i] == data)
return i;
return i;
}
public static void main(String args[]) {
int in[] = { 4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90 };
int post[] = { 4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25 };
Main tree = new Main();
System.out.println("Preorder Traversal of the tree is: ");
tree.printPreOrderTraversal(in, post);
}
}
실행 결과
Preorder Traversal of the tree is: 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90