C ++中二叉树中最深的奇数级节点的深度？

让我们首先定义表示包含 int 键及其左右节点子节点的树节点的结构。如果这是要创建的第一个节点，则它是根节点，否则是子节点。

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

接下来我们创建我们的createNode(int key)函数，它接受一个 int 键值并将其分配给节点的键成员。该函数返回指向创建的结构节点的指针。此外，新创建的节点的左右子节点设置为空。

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

接下来我们有 isLeaf(Node *currentNode) 函数，它接受一个节点并检查它是否有任何子节点。它根据节点是否为叶节点返回真或假。

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 << "最深奇数级叶节点的深度为： "<<deepestOddLvlDepth(root) << endl;
   return 0;
}

上面的代码将产生以下输出。

最深奇数级叶节点的深度为： 3