이번 튜토리얼에서는 이진 트리(binary tree)를 대각선 순회(diagonal traversal)했을 때 k번째 노드를 찾는 프로그램을 C++로 작성해 보겠습니다.
대각선 순회란 루트 노드에서 시작해 오른쪽 자식들을 따라 같은 대각선 상의 노드를 먼저 모두 방문하고, 왼쪽 자식은 다음 대각선으로 넘겨 탐색하는 방식입니다. 이 문제는 큐(queue) 자료구조를 활용하면 효율적으로 해결할 수 있습니다.
문제 해결 접근 방법
문제를 해결하기 위한 단계는 다음과 같습니다.
- 샘플 데이터로 이진 트리를 초기화합니다.
- 찾고자 하는 순서 값 k를 초기화합니다.
- 큐 자료구조를 사용해 이진 트리를 대각선으로 순회합니다.
- 노드를 방문할 때마다 k 값을 1씩 감소시킵니다.
- k가 0이 되면 해당 노드의 데이터를 반환합니다.
- 조건에 맞는 노드가 존재하지 않으면 -1을 반환합니다.
구현 예제 코드
전체 소스 코드는 아래와 같습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* getNewNode(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
int findDiagonalKthElement(Node* root, int k) {
if (root == NULL || k == 0) {
return -1;
}
int result = -1;
queue<Node*> q;
q.push(root);
q.push(NULL);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
if (temp == NULL) {
if (q.empty()) {
if (k == 0) {
return result;
}else {
break;
}
}
q.push(NULL);
}else {
while (temp) {
if (k == 0) {
return result;
}
k--;
result = temp->data;
if (temp->left) {
q.push(temp->left);
}
temp = temp->right;
}
}
}
return -1;
}
int main() {
Node* root = getNewNode(10);
root->left = getNewNode(5);
root->right = getNewNode(56);
root->left->left = getNewNode(3);
root->left->right = getNewNode(22);
root->right->right = getNewNode(34);
root->right->right->left = getNewNode(45);
root->left->right->left = getNewNode(67);
root->left->right->right = getNewNode(100);
int k = 9;
cout << findDiagonalKthElement(root, k) << endl;
return 0;
}동작 원리 살펴보기
- 큐에는 각 대각선의 시작점이 되는 왼쪽 자식 노드들이 저장됩니다.
NULL은 대각선과 대각선 사이의 경계를 나타내는 구분자 역할을 합니다.- 내부
while루프에서는 현재 노드에서 오른쪽 자식을 계속 따라가며 같은 대각선상의 노드들을 순서대로 방문하고, 방문할 때마다 k를 감소시켜 결과값을 갱신합니다. - 모든 대각선을 순회한 후에도 조건을 만족하지 못하면 -1을 반환합니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
67
예제 트리를 대각선 순회하면 10 → 56 → 34 → 45 → 5 → 22 → 67 → 100 → 3 순서로 방문하게 되며, 아홉 번째(k=9) 노드인 67이 출력됩니다.
마무리
지금까지 큐를 활용해 이진 트리의 대각선 순회에서 k번째 노드를 찾는 방법을 알아보았습니다. 이 알고리즘의 시간 복잡도는 O(N), 공간 복잡도는 O(N)입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.