好资源导航 » 文章资讯 » C++二叉树对角遍历中的第K个节点

C++二叉树对角遍历中的第K个节点

2023-06-15 10:09:03 73

在本教程中，我们将编写一个程序，在二叉树的对角线遍历中找到第k个节点。

让我们看看解决问题的步骤。

用一些样本数据初始化二叉树。

初始化数字k。

使用数据结构队列对角遍历二叉树。

减少每个节点上的k值。

当k变为0时返回节点。

如果没有这样的节点，则返回-1。

示例

让我们看看代码。

#include 
using namespace std;
struct Node {
   int data;
   Node *left, *right;
};
Node* getNewNode(int data) {
   Node* node = (Node*)malloc(sizeof(Node));
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
int findDiagonalKthElement(Node* root, int k) {
   if (root == NULL || k == 0) {
      return -1;
   }
   int result = -1;
   queue q;
   q.push(root);
   q.push(NULL);
   while (!q.empty()) {
      Node* temp = q.front();
      q.pop();
      if (temp == NULL) {
         if (q.empty()) {
            if (k == 0) {
               return result;
            }else {
               break;
            }
         }
         q.push(NULL);
      }else {
         while (temp) {
            if (k == 0) {
               return result;
            }
            k--;
            result = temp->data;
            if (temp->left) {
               q.push(temp->left);
            }
            temp = temp->right;
         }
      }
   }
   return -1;
}
int main() {
   Node* root = getNewNode(10);
   root->left = getNewNode(5);
   root->right = getNewNode(56);
   root->left->left = getNewNode(3);
   root->left->right = getNewNode(22);
   root->right->right = getNewNode(34);
   root->right->right->left = getNewNode(45);
   root->left->right->left = getNewNode(67);
   root->left->right->right = getNewNode(100);
   int k = 9;
   cout << findDiagonalKthElement(root, k) << endl;
   return 0;
}

输出结果

如果你运行上面的代码，那么你会得到下面的结果。

结论

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

返回顶部
514930285
czq8825@qq.com

C++二叉树对角遍历中的第K个节点

示例

结论

热门推荐

随机推荐