Tuyên bố vấn đề
Cho một cây nhị phân trong đó mỗi phần tử nút chứa một số. Nhiệm vụ là tìm tổng nhỏ nhất có thể từ nút lá này sang nút lá khác.
Ví dụ
Trong cây trên, đường dẫn phụ tối thiểu là -6 như sau:(- 4) + 3 + 2 + (-8) + 1
Thuật toán
Ý tưởng là duy trì hai giá trị trong các cuộc gọi đệ quy -
- Tổng đường dẫn từ gốc đến lá tối thiểu cho cây con bắt nguồn từ nút hiện tại
- Tổng đường dẫn tối thiểu giữa các lá
- Đối với mọi nút đã truy cập X, chúng ta phải tìm tổng số từ gốc đến lá tối thiểu trong các cây con bên trái và bên phải của X. Sau đó, cộng hai giá trị với dữ liệu của X và so sánh tổng với tổng đường dẫn tối thiểu hiện tại
Ví dụ
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int data;
struct node *left;
struct node *right;
} node;
node *newNode(int data) {
node *n = new node;
n->data = data;
n->left = NULL;
n->right = NULL;
return n;
}
int getMinPath(node *root, int &result) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return root->data;
}
int leftSum = getMinPath(root->left, result);
int rightSum = getMinPath(root->right, result);
if (root->left && root->right) {
result = min(result, root->data + leftSum + rightSum);
return min(root->data + leftSum, root->data + rightSum);
}
if (root->left == NULL) {
return root->data + rightSum;
} else {
return root->data + leftSum;
}
}
int getMinPath(node *root) {
int result = INT_MAX;
getMinPath(root, result);
return result;
}
node *createTree() {
node *root = newNode(2);
root->left = newNode(3);
root->right = newNode(-8);
root->left->left = newNode(5);
root->left->right = newNode(-4);
root->right->left = newNode(1);
root->right->right = newNode(10);
return root;
}
int main() {
node *root = createTree();
cout << "Minimum sum path = " << getMinPath(root) << endl;
return 0;
} Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Đầu ra
Minimum sum path = -6