ผลรวมสูงสุดของโหนดในต้นไม้แบบทวิภาคที่ไม่มีสองโหนดติดกันด้วย Dynamic Programming ใน C++

ในปัญหานี้ เราได้รับต้นไม้แบบทวิภาค (Binary Tree) ที่แต่ละโหนดมีค่า ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมสูงสุดของโหนดในต้นไม้แบบทวิภาคที่ไม่มีสองโหนดติดกันโดยใช้ Dynamic Programming

คำอธิบายปัญหา

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

ตัวอย่าง

อินพุต

เอาต์พุต

24

คำอธิบาย

องค์ประกอบที่พิจารณา: 8 + 5 + 9 + 2 = 24

แนวทางแก้ปัญหา

วิธีแก้ปัญหาคือการใช้แผนที่ (map) และหาผลรวมของโหนดที่ทำให้ได้ maxSum ทั้งโหนดและลูกของมันไม่สามารถพิจารณาสำหรับผลรวมได้ตามเงื่อนไขที่กำหนด ดังนั้นเราต้องตรวจสอบว่า ก่อนพิจารณาโหนดหนึ่ง เราต้องตรวจสอบว่าต้นไม้ย่อยของลูกมีองค์ประกอบบางอย่างที่เป็นผลรวมที่มากกว่าหรือไม่

การหาผลรวมของซับทรีพ่อ-ลูกเดียวกันหลายครั้งสำหรับแต่ละโหนดจะเพิ่มค่าใช้จ่ายในการคำนวณ และเพื่อจัดการกับสิ่งนี้ เราจะใช้การจดจำ (memorization) และเก็บ maxSum จนถึงโหนดในแผนที่ซึ่งสามารถนำกลับมาใช้ได้ภายหลัง

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

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#include <bits/stdc++.h> 
using namespace std; 

struct node{ 
    int data; 
    struct node *left, *right; 
}; 

struct node* newNode(int data){ 
    struct node *temp = new struct node; 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 

int findMaxSumBT(node* node, map<struct node*, int>& nodeSum); 

int sumSubTreeNodes(node* node, map<struct node*, int>& nodeSum){ 
    int maxSum = 0; 
    if (node->left) 
        maxSum += findMaxSumBT(node->left->left, nodeSum) + 
        findMaxSumBT(node->left->right, nodeSum); 
    if (node->right) 
        maxSum += findMaxSumBT(node->right->left, nodeSum) + 
        findMaxSumBT(node->right->right, nodeSum); 
    return maxSum; 
} 

int findMaxSumBT(node* node, map<struct node*, int>& nodeSum){ 
    if (node == NULL) 
        return 0; 
    if (nodeSum.find(node) != nodeSum.end()) 
        return nodeSum[node]; 
    int sumInclCurr = node->data + sumSubTreeNodes(node, nodeSum); 
    int sumExclCurr = findMaxSumBT(node->left, nodeSum) + 
    findMaxSumBT(node->right, nodeSum); 
    nodeSum[node] = max(sumInclCurr, sumExclCurr); 
    return nodeSum[node]; 
} 

int main(){ 
    node* root = newNode(9); 
    root->left = newNode(4); 
    root->right = newNode(7); 
    root->left->left = newNode(8); 
    root->left->right = newNode(5); 
    root->right->left = newNode(2); 
    map<struct node*, int> nodeSum; 
    cout << "Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is " << findMaxSumBT(root, nodeSum); 
    return 0; 
}

เอาต์พุต

Maximum sum of nodes in Binary tree such that no two are adjacent using Dynamic Programming is 24