백준 2263번 트리의 순회[C++]

1. 문제 풀이

 이진트리는 AVL임을 보장하는 조건이 나오지 않았습니다. 따라서 skewed 한 경우도 고려하여야 합니다. 우선 inorder와 postorder 순서를 통해 얻을 수 있는 정보가 있는지 확인해보아야 합니다. 문제에서 주어진 예제 코드는 노드가 3개뿐이라 분석하기엔 너무 작습니다. 정점 개수가 좀 더 많은 트리를 하나 세워서 확인해 보겠습니다.

 

정점의 개수 : 7

inorder : 4 1 3 6 5 2 7

postorder : 4 1 3 5 7 6

 

postorder를 통해서 처음 알 수 있는 사실은 제일 마지막 값인 6이 트리의 루트임을 알 수 있습니다.

 

inorder는 root node인 6을 기준으로 왼쪽은 left 부분 트리이고, 오른쪽은 right 부분 트리입니다. inorder에서 루트 노드의 등장 위치를 알 수 있으면 각 부분 트리의 크기를 계산할 수 있습니다. 그 크기를 postorder에 적용하게 된다면 각각의 부분트리의 루트노드를 알 수 있습니다. 부분 트리의 루트 노드는 현재 루트 노드 6의 child임을 파악할 수 있습니다.

 

결론적으로 inorder와 postorder의 범위값과 루트노드가 주어진다면 각 노드의 left, right child를 파악할 수 있습니다. 이를 분할정복으로 구현하였습니다. inorder에서 루트노드의 등장 위치를 O(1)로 접근하기 위해 각 노드마다의 등장 위치만 저장하였습니다.

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
int idx[100'005];
int postorder[100'005];

// 트리 
int l[100'005];
int r[100'005];

void find_tree(int ist, int ien, int pst, int pen, int cur){
  int k = idx[cur];
  int ls = k - ist, rs = ien - k;

  if(ls > 0){
    l[cur] = postorder[pst+ls-1];
    if(ls > 1) find_tree(ist, k-1, pst, pst+ls-2, l[cur]);
  }
  if(rs > 0){
    r[cur] = postorder[pen];
    if(rs > 1) find_tree(k+1, ien, pst+ls, pen-1, r[cur]);
  }
}

void preorder(int cur){
  if(cur == 0) return;
  cout << cur << ' ';
  preorder(l[cur]);
  preorder(r[cur]);  
}

int main() {
  fastio(nullptr, false);

  // input
  cin >> n;
  for(int i = 1; i <= n; i++){
    int node;
    cin >> node;
    idx[node] = i; // inorder는 순서값만 저장
  }

  for(int i = 1; i <= n; i++) cin >> postorder[i];

  // solve
  find_tree(1, n, 1, n-1, postorder[n]);

  // output
  preorder(postorder[n]);
}

 

3. 제출 결과