[알고리즘] 트리의 순회

구현 방식

• 후위 표기법의 가장 마지막으로 적힌 노드는 루트 노드임을 이용한다.
• 중위 표기법에서 루트노드의 왼쪽에 적힌 노드들은 모두 루트의 왼쪽 노드들이고 오른쪽에 적힌 노드들은 모두 루트의 오른쪽 노드들이다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

void solution(int N);
void preOrder(int inStart, int inEnd, int postStart, int postEnd);

vector<int> inorder;
vector<int> postorder;
map<int,int> inIdx;

int main() {

    int N;
    cin >> N;

    inorder = vector<int>(N);
    postorder = vector<int>(N);
    for (int i = 0; i < N; i++)
    {
        cin >> inorder[i];
        inIdx[inorder[i]] = i;
    }
    for (int i = 0; i < N; i++)
    {
        cin >> postorder[i];
    }
    solution(N);
    return 0;
}


void solution(int N)
{
    preOrder(0, N - 1, 0, N - 1);
}

void preOrder(int inStart, int inEnd,
              int postStart, int postEnd )
{
    if (inEnd < inStart || postEnd < postStart) return;
    cout << postorder[postEnd] << " ";

    int inRootIdx = inIdx[postorder[postEnd]];
    int leftSize = inRootIdx - inStart;
    int rightSize = inEnd - inRootIdx;


    preOrder(inStart, inRootIdx - 1, postStart, postStart + leftSize - 1);
    preOrder(inRootIdx + 1, inEnd, postEnd - rightSize, postEnd -1);

}