C++의 이진 트리에서 가장 깊은 홀수 레벨 노드의 깊이?

먼저 int 키와 왼쪽 및 오른쪽 노드 자식을 포함하는 트리 노드를 나타내는 구조체를 정의하겠습니다. 이것이 생성될 첫 번째 노드이면 루트 노드이고 그렇지 않으면 자식 노드입니다.

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

다음으로 int 키 값을 받아 노드의 키 멤버에 할당하는 createNode(int key) 함수를 만듭니다. 함수는 생성된 구조체 노드에 대한 포인터를 반환합니다. 또한 새로 생성된 노드의 왼쪽과 오른쪽 자식은 null로 설정됩니다.

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

다음으로 노드를 가져와 자식이 있는지 확인하는 isLeaf(Node *currentNode) 함수가 있습니다. 노드가 리프 노드인지 여부에 따라 true 또는 false를 반환합니다.

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

deepestOddLvlDepth(Node *currentNode, int currentLevel=0)은 currentNode와 currentLevel을 취합니다. currentLevel에 값이 전달되지 않은 경우 기본값은 0입니다. currentNode가 null이면 함수는 0을 반환합니다.

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

currentLevel은 기본 조건이 충족될 때까지 각 재귀 수준에서 1씩 증가합니다. 그런 다음 currentNode가 홀수 리프 노드인지 확인합니다. 그런 다음 가장 깊은 홀수 레벨 리프 노드 깊이를 찾을 때까지 left 및 rightChild를 순회합니다. leftChildDepth 및 rightChild 깊이의 최대값은 결과를 출력하기 위해 메인 함수로 반환됩니다.

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