백준 4256번 트리 - C++ 풀이

---

 

1. root 노드는 preorder[0]이다.
2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다.

 

1. root 노드는 preorder[0]이다.

 전위 순회 시 가장 먼저 방문하는 노드는 루트 노드이다.

 

2. inorder 결과에서 root보다 먼저 나온 노드들은 왼쪽 부트리를 이루고, 나중에 나온 노드들은 오른쪽 부트리를 이룬다.

 중위 순회 시 왼쪽 부트리 - 루트 - 오른쪽 부트리 순으로 방문한다. 전위 순회 결과에서 찾은 루트를 중위 순회 결과에서 찾는다. 그리고 루트보다 더 먼저 등장한 노드들로 왼쪽 부트리를 만들고, 루트보다 더 나중에 등장한 노드들로 오른쪽 부트리를 만드는 작업을 재귀적으로 반복해주면 원래 트리를 복원할 수 있다.

 

반응형

---

#include <iostream>
#include <cstring>

using namespace std;

int N;
int preorder[1001], inorder[1001], pos[1001];

void postorder(int pLo, int pHi, int iLo, int iHi) {
    if (pLo > pHi) return;
    
    int root = preorder[pLo];
    int lSize = pos[root] - iLo;
    
    postorder(pLo+1, pLo+lSize, iLo, pos[root]-1);
    postorder(pLo+lSize+1, pHi, pos[root]+1, iHi);
    
    cout << root << " ";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T; cin >> T;
    while (T--) {
        cin >> N;
        for (int i=0; i<N; i++) cin >> preorder[i];
        for (int i=0; i<N; i++) {
            cin >> inorder[i];
            pos[inorder[i]] = i;
        }
        
        postorder(0, N-1, 0, N-1);
        cout << "\n";
    }
  
    return 0;
}