[백준] No.2263 - 트리의 순회 (C++, 트리)

문제

 

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

2263번: 트리의 순회

 

풀이

 

solved.ac 난이도: Gold 3

 

 

이진트리의 순회 순서를 공부하기 좋은 문제이다.

 

이진트리의 순회 순서에는 3가지가 존재한다. 

3가지 순회의 이름은 루트 노드를 언제 방문하는지에 따라 지어졌다.

모든 순회는 항상 오른쪽 노드보다 왼쪽 노드를 먼저 방문한다. 

 

1. 전위 순회(preorder traverse): 루트 -> 왼쪽 -> 오른쪽

2. 중위 순회(inorder traverse): 왼쪽 -> 루트 -> 오른쪽

3. 후위 순회(postorder traverse): 왼쪽 -> 오른쪽 -> 루트

 

문제는 이중에서 중위 순회와 후위 순회가 주어진다.

중위 순회에서는 루트가 중간에, 후위 순회에서는 루트가 마지막에 방문됨을 이용해서 문제를 해결하자.

 

같은 문제를 해설한 종만북의 예제 트리를 통해 생각해보자.

 

중위: 9 12 16 27 36 54 72

후위: 12 9 16 36 72 54 27

 

후위에서는 루트 노드는 항상 마지막에 위치한다.

후위에서 찾은 루트를 통해 중위에서의 루트 위치를 찾아주자.

 

중위 순회에서 루트 기준의 왼쪽은 모두 왼쪽 노드들이고, 오른쪽은 루트 기준으로 오른쪽 노드들이다.

 

후위에서는 왼쪽 노드들 다음으로 오른쪽 노드를 방문하므로

중위에서 구한 왼쪽 노드들의 개수만큼이 후위 순회에서의 왼쪽 노드들이 된다. 왼쪽 노드 이후부터 루트의 바로 앞 노드까지가 후위의 오른쪽 노드이다.

 

이를 구현한 재귀함수에서는 루트를 먼저 출력한 후 왼쪽 노드들의 중위,후위에서의 범위를 전달하여 출력한다.

마지막으로 오른쪽 노드를 출력하여 전위 순회를 구현한다.

 

 

void PrintPreOrder(int in_l,int in_r,  int post_l, int post_r){
  if(in_l>in_r || post_l>post_r)
    return;
 
  int root = postorder[post_r];
  int in_root;
  cout<< root <<' ';
 
  if(post_r == post_l)
    return;
 
  for(int i=in_l; i<=in_r ; ++i)
    if(inorder[i] == root){
      in_root = i;
      break;
    }
 
  int left_size = in_root - in_l;
  PrintPreOrder(in_l,in_root-1 ,post_l , post_l+ left_size -1);  //왼쪽 부분
  PrintPreOrder(in_root+1,in_r , post_l+ left_size, post_r-1 );  //오른쪽 부분
  return;
}

 

 

코드