중위 순회로 트리 복원하기 (코드트리 2 + 1)

각 순회가 작동하는 과정

전위 순회 (preOrder): parent -> left -> right

중위 순회 (inOrder): left -> parent -> right

후위 순회 (postOrder): left -> right -> parent

중위 순회가 꼭 필요한 이유

먼저 중위 순회는 어떤 순회와 조합되더라도 꼭 있어야 한다. 왜냐하면 트리의 복원에서 가장 중요하게 여겨지는 것은 "어디까지가 왼쪽 자식이고, 어디서부터가 오른쪽 자식인가" 이기 때문이다. 그래서 중위 순회에서 parent 를 찾아서 해당 원소를 기준으로 왼쪽 오른쪽 서브 트리를 나눈다. (경계선이 되어줌)

후위 순회 혹은 전위 순회가 꼭 필요한 이유

위 과정을 확인하면, 전위 순회와 후위 순회의 첫 번째 원소 혹은 마지막 원소는 root 원소이다. (최종 parent)

두 가지 순회를 합하면

1. root 원소를 후위 or 전위 순회를 통해 알아내고
2. 해당 root 원소를 기준으로 왼쪽 트리와 오른쪽 트리를 나눈다.
3. 해당 왼쪽 트리와 오른쪽 트리 안에서도 후위 or 전위 순회를 바탕으로 해당 서브 트리의 root 원소를 알아내어 복원한다.

문제 풀어 보기

단계 1: 전체 루트 찾기

• 후위 순회의 마지막 원소는 4. 따라서 전체 트리의 루트(Root)는 4
• 중위 순회에서 4를 기준으로 나누면
  • 왼쪽 자식들: [1, 8, 7, 5]
  • 오른쪽 자식들: [2, 3, 6]

단계 2: 왼쪽 서브트리 복원 ([1, 8, 7, 5] 범위)

• 후위 순회에서 [1, 7, 8, 5] 중 가장 뒤에 있는 5가 루트
• 중위 순회에서 5를 기준으로 나누면 [1, 8, 7]이 모두 5의 왼쪽에 있음. (즉, 5의 오른쪽 자식은 없음)
• [1, 8, 7] 중 후위 순회 마지막인 8이 루트
• 중위 순회에서 8을 기준으로 1은 왼쪽, 7은 오른쪽 자식

단계 3: 오른쪽 서브트리 복원 ([2, 3, 6] 범위)

• 후위 순회에서 [2, 6, 3] 중 가장 뒤에 있는 3이 루트가 됨
• 중위 순회에서 3을 기준으로 2는 왼쪽, 6은 오른쪽 자식이 됨

최종 트리 모양

 

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-traversal-inference/description

2 + 1 설명 | 코드트리