โปรแกรม C++ หาเส้นทางผลรวมต่ำสุดระหว่างสองใบไม้ของต้นไม้ไบนารี

ข้อความโจทย์

กำหนดต้นไม้ไบนารีที่แต่ละโหนดมีตัวเลข งานคือการหาผลรวมต่ำสุดที่เป็นไปได้จากโหนดใบหนึ่งไปยังอีกโหนดใบหนึ่ง

ตัวอย่าง

ในต้นไม้ข้างต้น เส้นทางผลรวมต่ำสุดคือ -6 ดังนี้: (-4) + 3 + 2 + (-8) + 1

อัลกอริทึม

แนวคิดคือการรักษาค่าสองค่าในการเรียกฟังก์ชันเวียนเกิด:

• ผลรวมเส้นทางจากรากไปยังใบต่ำสุดสำหรับต้นไม้ย่อยที่รากอยู่ภายใต้โหนดปัจจุบัน
• ผลรวมเส้นทางต่ำสุดระหว่างใบไม้
• สำหรับโหนด X ที่เยี่ยมชมแต่ละอัน เราต้องหาผลรวมรากไปยังใบต่ำสุดในต้นไม้ย่อยซ้ายและขวาของ X จากนั้นบวกค่าทั้งสองกับข้อมูลของ X และเปรียบเทียบผลรวมกับผลรวมเส้นทางต่ำสุดปัจจุบัน

ตัวอย่างโค้ด C++

#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