C++ 전위 순회 배열로 BST의 후위 순회 구하기

문제 개요

이 문제에서는 이진 탐색 트리(BST)의 전위 순회(preorder traversal) 결과를 담고 있는 배열 preOrder[]가 주어집니다. 목표는 이 배열만으로 해당 BST의 후위 순회(postorder traversal) 결과를 구하는 것입니다.

먼저 예시를 통해 문제를 살펴보겠습니다.

입력

preOrder[] = {5, 2, 4, 7, 12}

출력

{4, 2, 12, 7, 5}

해결 접근 방법

가장 단순한 해결책은 주어진 전위 순회 배열로 BST를 직접 구성한 뒤, 완성된 트리를 후위 순회하는 것입니다. 이 방법으로도 정답을 얻을 수 있지만, 다음과 같이 더 효율적인 방법을 사용할 수 있습니다.

핵심 아이디어는 전위 순회 배열을 순회할 때 값의 하한과 상한(허용 범위)을 함께 전달하여 왼쪽 서브트리와 오른쪽 서브트리에 속한 값을 자연스럽게 구분하는 것입니다.

두 순회의 순서는 다음과 같습니다.

preOrder : Root -> Left -> Right
postOrder : Left -> Right -> Root

전위 순회의 첫 번째 원소는 항상 루트입니다. 루트에 대한 유효 범위는 {INT_MIN, Root}로 설정합니다. 이후 배열을 순회하면서 현재 값이 허용 범위를 벗어나면 해당 서브트리의 순회를 종료하고, 범위 안에 있는 동안에는 먼저 왼쪽 서브트리를 처리한 뒤 오른쪽 서브트리를 처리하고, 마지막에 현재 노드(루트)를 출력합니다. 이렇게 하면 후위 순회의 순서인 '왼쪽 → 오른쪽 → 루트'가 그대로 유지됩니다.

재귀 방식으로 구현한 솔루션입니다.

예제 코드

#include <iostream>
using namespace std;
void findPostOrderTraversalRec(int pre[], int n, int lowerLimit, int upperLimit, int& index){
    if (index == n)
        return;
    if (pre[index] < lowerLimit || pre[index] > upperLimit)
        return;
    int currNode = pre[index];
    index++;
    findPostOrderTraversalRec(pre, n, lowerLimit, currNode, index);
    findPostOrderTraversalRec(pre, n, currNode, upperLimit, index);
    cout<<currNode<<" ";
}
void findPostOrderTraversalFromPreOrder(int pre[], int n){
    int index = 0;
    findPostOrderTraversalRec(pre, n, -1000, 1000, index);
}
int main(){
    int pre[] = { 5, 2, 4, 7, 12 };
    int n = sizeof(pre) / sizeof(pre[0]);
    cout<<"PreOrder Traversal : \t";
    for(int i = 0; i < n ; i++)
        cout<<pre[i]<<" ";
    cout<<endl<<"Post Order Traversal : \t";
    findPostOrderTraversalFromPreOrder(pre, n);
    return 0;
}

실행 결과

PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5

반복문을 이용한 풀이

또 다른 방법은 반복문을 사용하는 것입니다. 전위 순회는 '루트 → 왼쪽 → 오른쪽', 후위 순회는 '왼쪽 → 오른쪽 → 루트' 순서라는 점을 활용합니다. 루트보다 처음으로 큰 값이 나타나는 위치, 즉 피벗(pivot)을 찾으면 그 앞부분은 왼쪽 서브트리, 그 이후는 오른쪽 서브트리로 나눌 수 있습니다. 이를 바탕으로 왼쪽 부분을 역순으로 출력하고, 다음으로 오른쪽 부분을 역순으로 출력한 뒤 마지막에 루트를 출력하면 후위 순회가 완성됩니다.

여기서 피벗은 루트 값보다 큰 첫 번째 원소의 인덱스를 의미합니다.

반복 방식으로 구현한 솔루션입니다.

예제 코드

#include <iostream>
using namespace std;
void findPostOrderTraversalFromPreOrder(int pre[], int n){
    int pivot = 0;
    for(int i = 1; i < n; i++){
        if (pre[0] <= pre[i]) {
            pivot = i;
            break;
        }
    }
    for(int i = pivot - 1; i > 0; i--){
        cout << pre[i] << " ";
    }
    for(int i = n - 1; i >= pivot; i--) {
        cout << pre[i] << " ";
    }
    cout << pre[0];
}
int main(){
    int pre[] = { 5, 2, 4, 7, 12 };
    int n = sizeof(pre) / sizeof(pre[0]);
    cout<<"PreOrder Traversal : \t";
    for(int i = 0; i < n ; i++)
        cout<<pre[i]<<" ";
    cout<<endl<<"Post Order Traversal : \t";
    findPostOrderTraversalFromPreOrder(pre, n);
    return 0;
}

실행 결과

PreOrder Traversal − 5 2 4 7 12
Post Order Traversal − 4 2 12 7 5