Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng ta là tìm Độ sâu tối thiểu của cây nhị phân.
Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con.
Độ sâu tối thiểu của cây nhị phân là đường đi ngắn nhất giữa nút gốc đến bất kỳ nút lá nào.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
Đầu ra
2
Phương pháp tiếp cận giải pháp
Giải pháp cho vấn đề là duyệt qua cây nhị phân và đếm chiều cao. Điều này có thể được thực hiện bằng cách gọi đệ quy nút con của nút cho mỗi nút không phải nút và trả về 1 cho mỗi nút lá.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
};
int findMinDepthBT(Node *currentNode) {
if (currentNode == NULL)
return 0;
if (currentNode->left == NULL && currentNode->right == NULL)
return 1;
if (!currentNode->left)
return findMinDepthBT(currentNode->right) + 1;
if (!currentNode->right)
return findMinDepthBT(currentNode->left) + 1;
return min(findMinDepthBT(currentNode->left),
findMinDepthBT(currentNode->right)) + 1;
}
Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
return 0;
} Đầu ra
The minimum depth of binary tree is 2
Cách tiếp cận này khá hiệu quả nhưng chúng ta có thể sử dụng các kỹ thuật truyền tải khác để tìm độ sâu tối thiểu hiệu quả hơn.
Một trong những cách tiếp cận như vậy là sử dụng trình duyệt theo thứ tự mức trong đó chúng ta duyệt qua mức cây theo mức. Và chúng tôi sẽ trả về số cấp mà chúng tôi gặp nút lá đầu tiên.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
struct lOrderQueue {
Node *node;
int depth;
};
int findMinDepthBT(Node *root) {
if (root == NULL)
return 0;
queue<lOrderQueue> levelOrder;
lOrderQueue deQueue = {root, 1};
levelOrder.push(deQueue);
while (levelOrder.empty() == false) {
deQueue = levelOrder.front();
levelOrder.pop();
Node *node = deQueue.node;
int depth = deQueue.depth;
if (node->left == NULL && node->right == NULL)
return depth;
if (node->left != NULL) {
deQueue.node = node->left;
deQueue.depth = depth + 1;
levelOrder.push(deQueue);
}
if (node->right != NULL) {
deQueue.node = node->right;
deQueue.depth = depth+1;
levelOrder.push(deQueue);
}
}
return 0;
}
Node* newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main() {
Node *root = newNode(5);
root->left = newNode(2);
root->right = newNode(9);
root->left->left = newNode(5);
root->left->right = newNode(1);
root->left->left->left = newNode(7);
root->left->left->right = newNode(3);
cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
return 0;
} Đầu ra
The minimum depth of binary tree is 2