Đề bài
Cho một cây nhị phân mà mỗi nút chứa một số. Nhiệm vụ là tìm tổng nhỏ nhất có thể từ một nút lá đến nút lá khác.
Ví dụ
Trong cây trên đường đi nhỏ nhất là -6 như sau: (-4) + 3 + 2 + (-8) + 1
Thuật toán
Ý tưởng là duy trì hai giá trị trong các lời gọi đệ quy:
- Tổng đường đi từ gốc đến lá nhỏ nhất cho cây con gốc tại nút hiện tại
- Tổng đường đi nhỏ nhất giữa các lá
- Với mỗi nút X được thăm, tìm tổng gốc-đáy nhỏ nhất trong cây con trái và phải của X. Cộng hai giá trị đó với dữ liệu của X, so sánh tổng với tổng đường đi nhỏ nhất hiện tại
Ví dụ mã nguồn
#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 biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum sum path = -6