คำชี้แจงปัญหา
กำหนดไบนารีทรีซึ่งแต่ละองค์ประกอบของโหนดประกอบด้วยตัวเลข ภารกิจคือการหาผลรวมขั้นต่ำที่เป็นไปได้จากโหนดปลายสุดหนึ่งไปยังอีกโหนดหนึ่ง
ตัวอย่าง
ในเส้นทางย่อยขั้นต่ำของทรีด้านบนคือ -6 ดังนี้:(-4) + 3 + 2 + (-8) + 1
อัลกอริทึม
แนวคิดคือการรักษาค่าสองค่าในการเรียกซ้ำ -
- ผลรวมของเส้นทางรากถึงใบขั้นต่ำสำหรับทรีย่อยที่รูทภายใต้โหนดปัจจุบัน
- ผลรวมเส้นทางขั้นต่ำระหว่างใบไม้
- สำหรับทุกโหนดที่เข้าชม X เราต้องหารากต่ำสุดถึงผลรวมใบในแผนผังย่อยด้านซ้ายและด้านขวาของ X จากนั้นเพิ่มค่าทั้งสองด้วยข้อมูลของ X แล้วเปรียบเทียบผลรวมกับผลรวมของเส้นทางต่ำสุดในปัจจุบัน
ตัวอย่าง
#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;
} เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Minimum sum path = -6
