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

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

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

  • 使用一些样例数据初始化二叉树。
  • 初始化数字 k。
  • 使用数据结构队列对角遍历二叉树。
    • 在每个节点上递减 k 的值。
    • 当 k 变为 0 时返回节点。
  • 如果没有这样的节点，则返回 -1。

示例

让我们看看代码。

 在线演示

#include <bits/stdc++.h>
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<Node*> 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;
}

输出

如果您运行以上代码，则会得到以下结果。

67

结论

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

更新时间：2021-04-09

69 次浏览

开启 职业生涯

完成课程获得认证

开始
广告