백준 2263번: 트리의 순회

Seungil Kim·2021년 11월 1일

PS

목록 보기

72/206

트리의 순회

아이디어

postorder의 맨 뒤에 나오는 숫자가 루트 노드이다. 이 숫자를 inorder에서 찾는다. inorder에서 찾은 루트 노드를 기준으로 왼쪽, 오른쪽에 나오는 숫자들이 각각 왼쪽 서브트리, 오른쪽 서브트리를 이룬다. 여기서 각각 서브트리가 몇개의 노드를 가지고 있는지 계산한다. 왼쪽 서브트리가 L개의 노드를 가지고 있고, 오른쪽 서브트리가 R개의 노드를 가지고 있다고 할 때, postorder에서 왼쪽부터 L개 노드는 왼쪽 서브트리를 이루고, 그 이후 R개 노드는 오른쪽 서브트리를 이룬다.

코드

#include <bits/stdc++.h>

using namespace std;

vector<int> inorder;
vector<int> postorder;
int N;

void solve(int is, int ie, int ps, int pe){
    if (is > ie) return;
    cout << postorder[pe] << ' ';
    
    int root = is;
    while (inorder[root] != postorder[pe]) root++;
    
    int lis, lie, lps, lpe; // left
    int ris, rie, rps, rpe; // right
    
    lis = is;
    lie = root - 1;
    ris = root + 1;
    rie = ie;
    
    lps = ps;
    lpe = ps + (lie-lis);
    rps = lpe + 1;
    rpe = pe-1;
    
    solve(lis, lie, lps, lpe);
    solve(ris, rie, rps, rpe);
}

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

    int x;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x;
        inorder.push_back(x);
    }
    for (int i = 0; i < N; i++) {
        cin >> x;
        postorder.push_back(x);
    }
    
    solve(0, N-1, 0, N-1);
    
    return 0;
}

설명

inorder의 시작, 끝 인덱스와 postorder의 시작, 끝 인덱스를 넘기면서 재귀호출한다. 이 때 postorder의 맨 뒤 노드 출력 -> 왼쪽 서브트리로 재귀호출 -> 오른쪽 서브트리로 재귀호출 순서로 진행한다.

맨 처음에는 vector를 계속 만들어서 넘겼다


#include <bits/stdc++.h>

using namespace std;

int N;

void solve(vector<int> inorder, vector<int> postorder, int size){
    if (size == 0) return;
    cout << postorder.back() << ' ';
    
    vector<int> li, lp, ri, rp;
    
    int root = 0;
    for (root; root < size; root++) {
        if (inorder[root] == postorder.back()) break;
    }

    int i = 0;
    for (i; i < root; i++) {
        lp.push_back(postorder[i]);
    }
    for (i; i < size-1; i++) {
        rp.push_back(postorder[i]);
    }
    i = 0;
    for (i; i < root; i++) {
        li.push_back(inorder[i]);
    }
    for (i = root+1; i < size; i++) {
        ri.push_back(inorder[i]);
    }

    solve(li, lp, lp.size());
    solve(ri, rp, rp.size());
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<int> inorder;
    vector<int> postorder;
    int x;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x;
        inorder.push_back(x);
    }
    for (int i = 0; i < N; i++) {
        cin >> x;
        postorder.push_back(x);
    }
    
    solve(inorder, postorder, N);
    
    return 0;
}