ค้นหาผลรวมทรีย่อยที่ใหญ่ที่สุดในทรีใน C++

ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือ ค้นหาผลรวมทรีย่อยที่ใหญ่ที่สุดในทรี

คำอธิบายปัญหา: ต้นไม้ไบนารีประกอบด้วยค่าบวกและค่าลบ และเราต้องหาทรีย่อยที่มีจำนวนโหนดสูงสุด

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ผลลัพธ์: 13

คำอธิบาย:

ผลรวมของทรีย่อยทางซ้ายคือ 7
ผลรวมของทรีย่อยขวาคือ 1
ผลรวมของต้นไม้คือ 13

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

ในการแก้ปัญหา เราจะดำเนินการตามคำสั่งหลังการสั่งซื้อ คำนวณผลรวมของโหนดทรีย่อยด้านซ้ายและทรีย่อยด้านขวา สำหรับโหนดปัจจุบัน ให้ตรวจสอบว่าผลรวมของโหนดของโหนดปัจจุบันมากกว่าผลรวมของทรีย่อยทางซ้ายหรือขวา สำหรับแต่ละโหนดจากลีฟถึงรูท ให้ค้นหาผลรวมสูงสุด

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <iostream>
using namespace std;

struct Node {
   int key;
   Node *left, *right;
};

Node* newNode(int key) {
   
   Node* temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return temp;
}

int calcSumTreeSumRec(Node* root, int&amp; ans) {
   
   if (root == NULL)  
      return 0;
   int currSum = root->key + calcSumTreeSumRec(root->left, ans)+ calcSumTreeSumRec(root->right, ans);
   ans = max(ans, currSum);

   return currSum;
}

int calcMaxSubTreeSum(Node* root)
{
   if (root == NULL)  
      return 0;
   int ans = -100;
   calcSumTreeSumRec(root, ans);
   return ans;
}

int main() {

   Node* root = newNode(5);
   root->left = newNode(-4);
   root->right = newNode(4);
   root->left->left = newNode(3);
   root->left->right = newNode(8);
   root->right->left = newNode(-5);
   root->right->right = newNode(2);

   cout<<"The largest subtree sum is "<<calcMaxSubTreeSum(root);
   return 0;
}

ผลลัพธ์

The largest subtree sum is 13