이 문제에서는 이진 트리의 중위 및 후위 순회가 제공됩니다. 우리의 임무는 트리의 후위 순회를 인쇄하는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
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 Explanation: the binary tree is :
이 문제를 해결하기 위해 간단한 솔루션은 주어진 순회를 사용하여 트리를 만든 다음 트리의 선주문 순회를 찾는 것입니다. 그러나 이 방법은 시스템에 대해 더 복잡합니다.
문제를 해결하는 더 효과적인 솔루션은 스택 데이터 구조를 사용하는 것입니다. 트리의 각 노드를 살펴보겠습니다. 트리의 루트는 후위 순회에서 마지막 항목입니다. 이제 이진 트리의 왼쪽 및 오른쪽 하위 트리를 분리해야 합니다. 우리는 트리의 루트 노드를 알고 있기 때문입니다. 후위 순회에서 루트 노드 앞의 모든 요소는 왼쪽 하위 트리이고 루트 이후의 모든 요소는 오른쪽 하위 트리입니다.
이와 같이 우리는 모든 요소를 찾아 스택에 노드를 저장하고 preorder traversal을 제공하는 스택의 인쇄 요소를 저장합니다.
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 ars[]){
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