이진 트리가 하나 주어졌을 때, 먼저 리프 노드(자식이 없는 노드)들을 모두 출력하고, 출력된 리프 노드들을 트리에서 제거한 뒤, 트리에 더 이상 노드가 남아 있지 않을 때까지 같은 과정을 반복하는 것이 이 문제의 목표입니다.
예시
아래와 같은 이진 트리가 주어졌다고 가정해 보겠습니다.
리프 노드를 제거하는 과정을 단계별로 진행하면, 각 단계에서 출력되는 노드는 다음과 같습니다.
6 7 9 13 14 3 4 2 1
접근 방식
이 문제는 DFS(깊이 우선 탐색)를 이용해 해결합니다.
먼저 모든 노드의 order 값을 0으로 초기화한 뒤, 후위 순회(postorder)를 수행하면서 각 노드에 두 자식 노드의 order 값 중 최댓값 + 1을 부여합니다. 이렇게 하면 리프 노드는 1, 그 바로 위 단계의 노드는 2, 그 다음은 3과 같이 아래에서부터 단계별로 값이 매겨집니다. 마지막으로 이 order 값을 기준으로 오름차순 정렬하면 리프 노드부터 차례대로 출력할 수 있습니다.
알고리즘
시작
1단계 -> 구조체 Node 정의
데이터 멤버: data, order, *left, *right
2단계 -> 구조체 Node* newNode(int data, int order) 정의
struct Node* node = new Node, node->data = data, node->order = order,
node->left = NULL, node->right = NULL, return (node)
함수 void postod(struct Node* node, vector>& v)
1단계 -> node == NULL이면
반환
2단계 -> postod(node->left, v) 호출 (왼쪽 자식 먼저 순회)
3단계 -> postod(node->right, v) 호출 (이어서 오른쪽 자식 순회)
4단계 -> node->right == NULL && node->left == NULL이면
node->order를 1로 설정
v.push_back(make_pair(node->order, node->data))
그렇지 않으면
node->order = max((node->left)->order, (node->right)->order) + 1
v.push_back(make_pair(node->order, node->data))
조건문 종료
함수 void printLeafNodes(int n, vector>& v)
1단계 -> sort(v.begin(), v.end())로 벡터 정렬
2단계 -> i = 0부터 i < n까지 i++ 반복
v[i].first == v[i + 1].first이면
v[i].second를 공백과 함께 출력
그렇지 않으면
v[i].second를 출력하고 줄바꿈
반복문 종료
main() 함수
1단계 -> 루트 노드 생성: struct Node* root = newNode(1, 0)
2단계 -> n = 9로 선언 및 설정
3단계 -> postod(root, v) 호출
4단계 -> printLeafNodes(n, v) 호출
종료 예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
int order;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data, int order){
struct Node* node = new Node;
node->data = data;
node->order = order;
node->left = NULL;
node->right = NULL;
return (node);
}
void postod(struct Node* node, vector<pair<int, int>>& v){
if (node == NULL)
return;
/* 왼쪽 자식부터 순회 */
postod(node->left, v);
/* 이어서 오른쪽 자식 순회 */
postod(node->right, v);
// 현재 노드가 리프 노드라면 order는 1
if (node->right == NULL && node->left == NULL) {
node->order = 1;
// order 값과 노드 값으로 pair 생성
v.push_back(make_pair(node->order, node->data));
} else {
node->order = max((node->left)->order, (node->right)->order) + 1;
v.push_back(make_pair(node->order, node->data));
}
}
void printLeafNodes(int n, vector<pair<int, int>>& v){
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
if (v[i].first == v[i + 1].first)
cout << v[i].second << " ";
else
cout << v[i].second << "\n";
}
}
int main(){
struct Node* root = newNode(1, 0);
root->left = newNode(2, 0);
root->right = newNode(3, 0);
root->left->left = newNode(4, 0);
root->left->right = newNode(6, 0);
root->right->left = newNode(14, 0);
root->right->right = newNode(9, 0);
root->left->left->left = newNode(7, 0);
root->left->left->right = newNode(13, 0);
int n = 9;
vector<pair<int, int>> v;
postod(root, v);
printLeafNodes(n, v);
return 0;
}출력 결과
이 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
6 7 9 13 14 3 4 2 1
첫 번째 줄의 6, 7, 9, 13, 14는 order 값이 1인 리프 노드, 두 번째 줄의 3, 4는 order 값이 2인 노드, 세 번째 줄의 2는 order 값이 3인 노드, 마지막 줄의 1은 order 값이 4인 루트 노드를 의미합니다. 이처럼 order 값을 활용하면 리프 노드를 제거해 가는 과정을 실제로 트리를 수정하지 않고도 단계별로 출력할 수 있습니다.