Trong hướng dẫn này, chúng ta sẽ học cách tìm nút cấp lẻ sâu nhất trong cây nhị phân.
Điều này tương tự với việc tìm độ sâu của cây nhị phân. Ở đây, chúng ta phải đáp ứng thêm một điều kiện nữa, tức là mức hiện tại có phải là mức lẻ hay không.
Hãy xem các bước để giải quyết vấn đề.
-
Khởi tạo cây nhị phân với dữ liệu giả.
-
Viết một hàm đệ quy để tìm nút cấp lẻ sâu nhất trong cây nhị phân.
-
Nếu nút hiện tại là nút lá và mức là lẻ, thì hãy trả về mức hiện tại.
-
Khác trả về giá trị tối đa của nút trái và nút phải với các lệnh gọi hàm đệ quy.
-
-
In nút mức lẻ sâu nhất.
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn thực thi đoạn mã trên, bạn sẽ nhận được kết quả sau.
3
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.