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に値が渡されない場合、currentLevelのデフォルト値は0です。 currentNodeがnullの場合、関数は0を返します。

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

currentLevelは、基本条件が満たされるまで、再帰レベルごとに1ずつ増加します。次に、currentNodeが奇数リーフノードであるかどうかを確認します。次に、最も深い奇数レベルの葉ノードの深さが見つかるまで、leftChildと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