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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

如果您在本教程中有任何疑问，请在评论部分提出。

更新于：2021年1月27日

78 次查看

开启您的职业生涯

完成课程获得认证

开始学习
广告