Trong hướng dẫn này, chúng ta sẽ viết một chương trình tìm nút thứ k trong đường chéo của cây nhị phân.
Hãy xem các bước để giải quyết vấn đề.
- Khởi tạo cây nhị phân với một số dữ liệu mẫu.
- Khởi tạo số k.
- Duyệt cây nhị phân theo đường chéo bằng cách sử dụng hàng đợi cấu trúc dữ liệu.
- Giảm giá trị của k trên mỗi nút.
- Trả về nút khi k trở thành 0.
- Trả về -1 nếu không có nút như vậy.
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
67
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.