[백준OJ] 4256번 트리

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

4256번: 트리

---

 

풀이

트리의 전위순회, 후위순회, 중위순회를 이해하고 문제를 해결하면 간편하다.

먼저 예시2번을 트리로 그려보자.바이너리 트리에서 왼쪽자식의 순서가 먼저라 했으니,그려보면 아래와 같이 변한다.

여기서 중위순회를 돌면 5 6 8 4 3 2 1 7 이 된다. 그림을 보면 아! 싶은게 떠오를것이다. 맞다. 위의 트리를 눌러보면

아래와 같이 중위순위 순서가 된다.

 

따라서 여기서 후위순회의 결과를 찾기 위해선, 먼저 해당 서브트리의 루트를 찾는다. 처음은 전체 바이너리 트리의 루트를 찾아야하므로, 전위순회의 결과의 맨 앞 (3) 이 된다. 이 루트노드의 인덱스를 중위 순회에서 찾은 뒤, 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀함수를 호출해준다.

순서는 어차피 왼쪽자식이 우선이므로, 재귀를 호출할때마다 해당 서브트리의 루트노드는, 전위순회에서 한칸씩 앞으로 전진하면 된다.

현재 서브트리에서 재귀함수를 모두 마쳤다면, 현재 서브트리의 루트노드를 출력하면 후위순회의 결과가 완료된다.

물론 베이스케이스는 노드가 존재하지 않으면 RETURN 을 해주면된다.

 

반응형

 

코드

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

int preorder[1001];
int inorder[1001];
int n, t, cnt = 0;

void postorder(int left, int right) {
	if (left > right) {
		return;//베이스 케이스
	}
	int nodeInd;
    //현재 서브트리의 루트 검색
	for (int i = left; i <= right; i++) {
		if (preorder[cnt] == inorder[i]) {
			nodeInd = i;
			cnt++;//전위순회의 개념을 이용해서,다음 서브트리의 루트를 구하기위해 ++를 해준다.
			break;
		}

	}
	postorder(left, nodeInd - 1);//왼쪽 서브트리에 대한 재귀
	postorder(nodeInd + 1, right);//오른쪽 서브트리에 대한 재귀
	cout << inorder[nodeInd] << " ";//자기자신 출력
}

int main() {
	cin >> t;
	while (t--) {
		cin >> n;
		cnt = 0;
		for (int i = 0; i < n; i++) {
			cin >> preorder[i];
		}
		for (int i = 0; i < n; i++) {
			cin >> inorder[i];
		}
		postorder(0, n - 1);
		cout << "\n";
	}

	return 0;
}