[백준/C++] 트리의 순회

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 트리의 규칙을 잘 찾으면 해결할 수 있는 문제다.

 

인오더는 중위 순회로 (왼쪽) -> (루트) -> (오른쪽)

프리오더는 전위 순회로 (루트) -> (왼쪽) -> (오른쪽)

포스트오더는 후위 순회로 (왼쪽) -> (오른쪽) -> (루트)

순서로 탐색을 한다.

 

여기서 아래 그림을 예로 들어 생각해 보자

그러면 우리는 포스트오더가 항상 맨 마지막에 루트 노드가 오기 때문에 포스트오더의 마지막 노드는 프리오더에서 맨 처음에 나오는 루트 노드라는 사실을 알 수 있다.

 

즉, 아래 그림과 같이 처음에 탐색을 한다.

 이를 이용하면 인오더를 3구간 즉, (왼쪽), (루트), (오른쪽)으로 구분할 수 있고, 인오더의 3구간을 이용하면 포스트 오더도 마찬가지로 3 구간으로 나눌 수 있다.

 

이후 똑같은 방법으로 탐색을 이어나가면 된다.

 

프리오더에서 루트노드 이후에 탐색을 하는 부분은 왼쪽이므로 인오더와 포스트오더의 [3, 2, 4] , [3, 4, 2]를 탐색 하면

똑같은 방법으로 포스트 오더의 마지막인 2가 앞으로 오고 인오더의 3구간의 크기를 이용해 (왼쪽), (오른쪽), (루트)를 구분할 수 있게 된다.

 

이러한 방식을 계속 하면

최종적으로 이와 같은 프리오더를 구할 수 있게 된다.

 

+ 이때, 구간을 복사하면 메모리가 초과되기 때문에 인오더의 구간과 포스트오더의 구간을 이용해 어느 범위가 왼쪽 자식인지 알리는 방식으로 코드를 구현했다. (인오더의 st, ed구간, 포스트오더의 st, ed구간)

 

​

[아이디어 정리]

1. 포스트오더의 맨 마지막 노드가 루트노드이므로 이를 이용해 인오더에서 (왼쪽) (오른쪽) 구간의 원소를 구할 수 있다.
2. 왼쪽 오른쪽 구간이 구분 됐으므로 왼쪽 구간부터 탐색을 재귀적으로 이어나간다.
3. 프리오더를 구하기 위해 루트노드 출력, DFS(왼쪽탐색), DFS(오른쪽탐색)을 반복해 구하면 된다.
   

 

 

 

Code

 

 

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

void DFS(vector<int> &inTree, vector<int> &postTree, int inTreeSt, int inTreeEnd, int postTreeSt,int postTreeEnd, vector<int> &index)
{
	int inTreeSize = 0, rInTreeSize=0;
	int rNextInTreeSt;
	int i = index[postTree[postTreeEnd]];
	inTreeSize = i-inTreeSt;
	rNextInTreeSt = i + 1;
	rInTreeSize = inTreeEnd - i;
	cout << postTree[postTreeEnd]<<" ";
	if (inTreeSize>0) {
		//왼쪽 자식이 있다는 뜻
		DFS(inTree,postTree,inTreeSt,inTreeSt+inTreeSize-1,postTreeSt,postTreeSt+inTreeSize-1,index);
	}
	if (rInTreeSize>0) {
		// 오른쪽 자식이 있다는 뜻
		DFS(inTree, postTree, rNextInTreeSt , rNextInTreeSt +rInTreeSize-1, postTreeEnd-rInTreeSize, postTreeEnd-1,index);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;
	vector<int> inTree(n);
	vector<int> postTree(n);
	vector<int> index(n+1,0);
	for (int i = 0; i < n; i++)
	{
		cin >> inTree[i];
		index[inTree[i]] = i;
	}
	for (int i = 0; i < n; i++)
		cin >> postTree[i];
	DFS(inTree, postTree,0,n-1,0,n-1,index);
	return 0;
}

 

---

처음에 시간이 오래걸려서 왜 그런가 했는데, 포스트 오더를 이용해 인오더의 루트노드 위치를 찾는 방법에서 시간이 오래걸렸다. 그래서 index의 위치를 미리 저장해 O(1)로 찾을 수 있도록 해 더 빠르게 해결했다.

메모리가 좋으면 머리가 고생을 안해...

 

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