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

이진 트리에서 가장 깊은 홀수 레벨(odd level)에 위치한 리프 노드의 깊이를 구하는 알고리즘을 C++로 구현해 보겠습니다. 먼저 int형 키 값과 왼쪽·오른쪽 자식 노드 포인터를 담는 트리 노드 구조체부터 정의합니다. 최초로 생성되는 노드는 루트 노드가 되며, 이후 생성되는 노드들은 자식 노드로 연결됩니다.

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

1. 노드 생성 함수 — createNode()

createNode(int key) 함수는 int형 키 값을 인자로 받아 새 노드의 key 멤버에 할당한 뒤, 생성된 Node 구조체의 포인터를 반환합니다. 새로 만들어진 노드의 왼쪽·오른쪽 자식은 모두 NULL로 초기화됩니다.

Node* createNode(int data){
   Node* node = new Node;
   node->data = data;
   node->leftChild = node->rightChild = NULL;
   return node;
}

2. 리프 노드 판별 함수 — isLeaf()

isLeaf(Node *currentNode) 함수는 전달받은 노드에 자식이 있는지 검사하여, 해당 노드가 리프 노드인 경우 true를, 아니면 false를 반환합니다.

bool isLeaf(Node *currentNode){
   return (currentNode->leftChild == NULL &&
   currentNode->rightChild == NULL);
}

3. 깊이 계산 함수 — deepestOddLvlDepth()

deepestOddLvlDepth(Node *currentNode, int currentLevel=0) 함수는 현재 노드와 현재 레벨을 인자로 받습니다. currentLevel에는 기본값 0이 설정되어 있어 호출 시 값을 생략할 수 있습니다. currentNode가 NULL이면 함수는 0을 반환합니다.

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
   if ( currentNode == NULL)
      return 0;

재귀 호출이 한 단계 진행될 때마다 currentLevel이 1씩 증가하다가, 기저 조건(base condition)을 만나면 탐색이 종료됩니다. 이후 현재 노드가 홀수 레벨에 있는 리프 노드인지 확인하고, 왼쪽과 오른쪽 자식을 계속 순회하며 가장 깊은 홀수 레벨 리프 노드의 깊이를 찾습니다. 마지막으로 leftChildDepth와 rightChildDepth 중 더 큰 값을 main 함수로 반환하여 결과를 출력하게 됩니다.

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
   if ( currentNode == NULL)
      return 0;
      currentLevel ++;
   if ( currentLevel % 2 != 0 && isLeaf(currentNode))
      return currentLevel;
   int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
   int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
   return max(leftChildLevel,rightChildLevel);
}

전체 예제 코드

지금까지 설명한 내용을 바탕으로, 이진 트리에서 가장 깊은 홀수 레벨 리프 노드의 깊이를 구하는 전체 구현은 다음과 같습니다.

#include<iostream>
using namespace std;
struct Node{
   int key;
   struct Node *leftChild, *rightChild;
};
Node* createNode(int key){
   Node* node = new Node;
   node->key = key;
   node->leftChild = node->rightChild = NULL;
   return node;
}
bool isLeaf(Node *currentNode){
   return (currentNode->leftChild == NULL &&
   currentNode->rightChild == NULL);
}
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
   if ( currentNode == NULL)
      return 0;
      currentLevel ++;
   if ( currentLevel % 2 != 0 && isLeaf(currentNode))
      return currentLevel;
      int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
      int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
      return max(leftChildLevel,rightChildLevel);
}
int main(){
   Node *root = createNode(15);
   root->leftChild = createNode(33);
   root->rightChild = createNode(18);
   root->rightChild->leftChild = createNode(19);
   root->rightChild->rightChild = createNode(20);
   root->rightChild->rightChild->leftChild = createNode(28);
   root->rightChild->rightChild->rightChild = createNode(29);
   cout << "The depth of the deepest odd level leaf node is: "<<deepestOddLvlDepth(root) << endl;
   return 0;
}

실행 결과

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

The depth of the deepest odd level leaf node is: 3

예제 트리에서 루트 노드는 1레벨, 그 아래 자식들은 2레벨, 손자 노드들은 3레벨에 위치합니다. 이 중 3레벨(홀수 레벨)에 있는 리프 노드인 28과 29가 발견되므로, 결과적으로 가장 깊은 홀수 레벨 리프 노드의 깊이는 3이 됩니다.