C++로 이진 트리에서 가장 깊은 홀수 레벨 노드의 깊이 구하기

이 튜토리얼에서는 이진 트리(binary tree)에서 가장 깊은 홀수 레벨 노드를 찾는 방법을 배워보겠습니다.

이 문제는 이진 트리의 깊이(depth)를 구하는 것과 유사하지만, 한 가지 조건이 추가됩니다. 바로 현재 레벨이 홀수인지 함께 확인해야 한다는 점입니다.

그럼 문제를 해결하는 단계를 하나씩 살펴보겠습니다.

• 더미 데이터로 이진 트리를 초기화합니다.

• 이진 트리에서 가장 깊은 홀수 레벨 노드를 찾는 재귀 함수를 작성합니다.

  • 현재 노드가 리프 노드이고 레벨이 홀수라면 현재 레벨을 그대로 반환합니다.

  • 그렇지 않다면 왼쪽 자식과 오른쪽 자식에 대해 재귀 호출을 수행한 뒤, 두 결과 중 최댓값을 반환합니다.

• 구해진 가장 깊은 홀수 레벨의 값을 출력합니다.

예제 코드

위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
struct Node* newNode(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
int oddLeafDepthInTree(struct Node *root, int level) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL && level % 2 == 1) {
        return level;
    }
    return max(oddLeafDepthInTree(root->left, level + 1), oddLeafDepthInTree(root->right, level + 1));
}
int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->right = newNode(8);
    int level = 1, depth = 0;
    cout << oddLeafDepthInTree(root, level) << endl;
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

3

결과 분석

예제 트리에서 루트 노드는 레벨 1에 위치하며, 자식으로 내려갈 때마다 레벨이 1씩 증가합니다. 리프 노드인 4는 레벨 3(홀수)에 있고, 노드 7과 8은 각각 레벨 4(짝수)에 있습니다. 따라서 홀수 레벨에 있는 리프 노드 중 가장 깊은 곳은 노드 4가 속한 레벨 3이며, 함수는 3을 반환하게 됩니다.

마무리

이번 튜토리얼에서는 재귀 함수를 활용해 이진 트리에서 가장 깊은 홀수 레벨에 있는 리프 노드의 깊이를 구하는 방법을 알아보았습니다. 핵심은 트리를 순회하면서 리프 노드 여부와 레벨의 홀짝을 동시에 검사하는 것입니다. 시간 복잡도는 모든 노드를 한 번씩 방문하므로 O(N)입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.