[BOJ알고리즘, C++]#4256_트리, 트리의 순회, 두 가지 순회를 통해 다른 하나의 순회 찾기 유형

 

#1. 문제

https://www.acmicpc.net/problem/4256

 

---

 

#2. 풀이

 

1. 트리의 순회

[자료구조]#5_트리

트리 자료구조는 세 가지 순회 방법을 갖습니다. 모두 현재 노드를 기준으로 (1) 전위 순회(루트->왼쪽->오른쪽), (2) 중위 순회(왼쪽->루트->오른쪽), 그리고 (3) 후위 순회(왼쪽->오른쪽->루트)가 있습니다. 대부분의 경우, 주어진 트리 자료구조의 두 가지 순회 내용을 알려주고, 다른 하나의 순회 내용을 구하는 문제가 나옵니다.

 

2. 전위 순회에서 루트 노드 찾고, 중위 순회에서 왼쪽과 오른쪽 서브트리 분할!

전위 순회: [ 루트 노드 | 왼쪽 서브트리 | 오른쪽 서브트리 ]
중위 순회: [ 왼쪽 서브트리 | 루트 노드 | 오른쪽 서브트리 ]

1. 현재 전위 순회 목록의 첫 번째 노드는 루트 노드입니다. 이어서, 두 번째 노드는 왼쪽 서브트리의 루트 노드가 됩니다. 이를 활용해, 전위 순회 목록을 차례대로 순회하며 중위 순회 목록에서 해당 노드를 찾아 왼쪽 서브트리와 오른쪽 서브트리로 분할합니다. 이어서, 현재 전위 순회 목록의 두 번째 노드는 왼쪽 서브트리의 루트 노드가 되며, 이전 중위 순회 목록에서 분할되어 나온 '왼쪽 서브트리'의 루트 노드가 됩니다.
2. 전위 순회를 차례대로 순회 -> 현재 위치의 노드가 루트 노드가 되어 중위 순회 목록을 분할 -> 어차피 다음 위치의 노드는 왼쪽 서브트리의 루트 노드가 되어 중위 순회 목록에서 분할되어 나온 왼쪽 서브트리에서 해당 노드를 찾아서 다시 분할....-> 왼쪽 서브트리가 끝나고 전위 순회 목록에서 그다음 위치의 노드는 또 오른쪽 서브트리의 루트 노드가 된다. 이 과정을 반복하면 자연스럽게 '왼쪽 서브트리' -> '오른쪽 서브트리' -> 루트 노드 순서가 되어 '후위 순회' 목록을 만들 수 있게 됩니다.

 

---

 

#3. 코드

/*
    @문제 : 이진트리(각 노드의 차수가 최대 2이하로 유지)의 전위 순회와 중위 순회를 통해 후위 순회를 구해라
    @설명
            1. 전위 순회 : [ 루트 노드 | 왼쪽 서브트리 루트 노드 | 오른쪽 서브트리 루트 노드 ]
               중위 순회 : [ 왼쪽 서브트리 | 루트 노드 | 오른쪽 서버트리 ]
               후위 순회 : [ 왼쪽 서브트리 | 오른쪽 서브트리 | 루트 노드 ]
            2. 전위 순회를 차례대로 순회하며, 현재 루트 노드, 왼쪽 서브트리 루트 노드, 오른쪽 서브트리 루트 노드를 찾는다.
            3. 중위 순회에서 '전위 순회의 현재 루트 노드'를 찾아서, 왼쪽 서브트리 오른쪽 서브 트리 분할
            4. 그러면 자연스레, 전위 순회의 다음 인덱스 위치에 있는 노드는 왼쪽 서브트리의 루트 노드가 된다.
               따라서, 왼쪽 서브 트리에 대한 재귀 호출을 진행하면, 이 루트 노드를 활용해 다시 중위 순회 목록에서 왼쪽 서브트리 오른쪽 서브트리 분할
               위 과정을 반복
*/

#include <iostream>
#include <vector>
using namespace std;

int T, n;
vector<int> pre;
vector<int> in;

int FindRootNodeInInOrder(vector<int>& in, int start, int end, int root)
{
    for(int i=start; i<=end; ++i)
    {
        if(in[i] == root)
            return i;
    }
    return -1;
}

void FindPost(vector<int>& pre, vector<int>& in, int start, int end, int& idx)
{
    if(start > end) return;

    // #1. 전위 순회 현재 루트 노드 -> 중위 순회에서 찾기
    int root = FindRootNodeInInOrder(in, start, end, pre[idx++]);

    // #2. 분할 후 왼쪽 서브트리
    FindPost(pre, in, start, root-1, idx);

    // #3. 분할 후 오른쪽 서브트리
    FindPost(pre, in, root+1, end, idx);

    // #4. 루트 노드 출력
    if(root != -1) cout << in[root] << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    while(T--)
    {
        cin >> n;
        pre.clear();
        in.clear();
        for(int i=0; i<n; ++i)
        {
            int num;
            cin >> num;

            pre.push_back(num);
        }
        for(int i=0; i<n; ++i)
        {
            int num;
            cin >> num;

            in.push_back(num);
        }
        int idx =0;
        FindPost(pre, in, 0, n-1, idx);
        cout << '\n';
    }

    return 0;
}

 

---