数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时装研究
法律研究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 次浏览
广告