2263번: 트리의 순회
첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
www.acmicpc.net
다음과 같은 트리가 있을 때, 인오더와 포스트오더로 나타내면 아래와 같다.
InOrder : 4 - 2 - 5 - 1 - 6 - 3 - 7
PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1
포스트오더로 나열하면 가장 오른쪽에 있는 값은 트리의 루트가 된다.
포스트오더는 왼쪽 노드 - 오른쪽 노드 - 가운데 노드 순서대로 순회하기 때문이다.
PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1
인오더에서는 루트를 기준으로 왼쪽은 왼쪽 자식 트리, 오른쪽은 오른쪽 자식 트리이다.
인오더는 왼쪽 노드 - 가운데 노드 - 오른쪽 노드 순서대로 순회하기 때문이다.
InOrder : 4 - 2 - 5 - 1 - 6 - 3 - 7
정리하자면, 인오더와 포스트오더의 정보가 주어졌을 때,
포스트오더를 통해서는 트리의 루트를 알 수 있고, 인오더를 통해서는 왼쪽 자식 트리와 오른쪽 자식 트리를 알 수 있다.
이제 이렇게 얻은 정보로 프리오더의 순서를 알 수 있다.
프리오더는 가운데 노드 - 왼쪽 노드 - 오른쪽 노드 순서대로 순회한다.
따라서 포스트오더에서 가장 오른쪽에 있던 루트 노드가 프리오더에서는 가장 먼저 오게 된다.
PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1
PreOrder : 1 - ○ - ○ - ○ - ○ - ○ - ○
그렇다면 1 다음으로는 어떤 수가 와야 할까?
가운데 노드를 방문한 다음에는 왼쪽 자식 트리를 똑같은 방법으로 순회해야 한다.
마찬가지로 왼쪽 자식 트리의 루트 노드를 먼저 방문하고 그 다음 왼쪽 노드, 오른쪽 노드를 차례로 방문한다.
왼쪽 자식 노드에서는 2가 루트노드이므로 1 다음에는 2를 순회하게 된다.
마찬가지로 인오더에서 2를 기준으로 왼쪽에 있는 값들은 왼쪽 자식 노드, 오른쪽에 있는 값들은 오른쪽 자식 노드에 해당함을 알 수 있다.
PostOrder : 4 - 5 - 2
PreOrder : 1 - 2 - ○ - ○ - ○ - ○ - ○
InOrder : 4 - 2 - 5
이런식으로 계속 포스트오더에서 트리 노드를 찾고, 인오더에서는 트리 노드를 기준으로 좌우로 나누어 왼쪽 자식 트리와 오른쪽 자식 트리를 찾는방식으로 프리오더의 순서를 채워넣으면 된다.
이렇게 분할하고 반복되는 과정은 재귀를 이용하게 손쉽게 구현할 수 있다.
그렇다면 언제까지 반복하는가?
트리에 노드가 하나밖에 없을때까지 반복한다. 즉, 더 이상 왼쪽 자식 트리와 오른쪽 자식 트리로 나눌 수 없을 때까지 반복한다.
소스코드 :
'BOJ' 카테고리의 다른 글
| [백준 1208번] 부분수열의 합 2 (java) (0) | 2021.03.09 |
|---|---|
| [백준 2630번] 색종이 만들기 (java) (0) | 2021.03.09 |
| [백준 1992번] 쿼드트리 (java) (0) | 2021.03.09 |
| [백준 8983번] 사냥꾼 (java) (0) | 2021.03.08 |
| [백준 2873번] 롤러코스터 (java) (0) | 2021.03.08 |