home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ผลรวมสูงสุด BST ในทรีไบนารีใน C ++

สมมติว่าเรามีรูทแบบไบนารี เราต้องหาผลรวมสูงสุดของโหนดทั้งหมดของทรีย่อยใดๆ ซึ่งเป็น Binary Search Tree (BST) ด้วย

ดังนั้นหากอินพุตเป็นแบบนั้น

ผลรวมสูงสุด BST ในทรีไบนารีใน C ++

จากนั้นผลลัพธ์จะเป็น 20 นี่คือผลรวมของโหนดทั้งหมดใน BST ที่เลือก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • สร้างหนึ่งบล็อกที่เรียกว่า Data ซึ่งจะเก็บสมาชิกบางคนเช่น sz, maxVal, minVal, ok, sum กำหนดตัวเริ่มต้นสำหรับข้อมูลด้วย ซึ่งจะเรียงลำดับตามนี้ (sz, minVal, maxVal, ok และตั้งค่าผลรวมเป็น 0)

  • ยกเลิก :=0

  • กำหนดวิธีการที่เรียกว่าแก้ปัญหา () ซึ่งจะเป็นการรูทต้นไม้

  • ถ้าไม่ใช่โหนดไม่ใช่ศูนย์ หรือ val ของโหนดเท่ากับ 0 แล้ว −

    • ส่งคืนข้อมูลใหม่โดยกำหนดค่าเริ่มต้นโดย (0, inf, -inf, true)

  • ซ้าย :=แก้ (ซ้ายของโหนด)

  • right =แก้ (ด้านขวาของโหนด)

  • สร้างหนึ่งอินสแตนซ์ประเภทข้อมูลที่เรียกว่าcurr

  • curr.ok :=เท็จ

  • ถ้าโหนด -> val>=right.minVal แล้ว −

    • ผลตอบแทนสกุลเงิน

  • ถ้าโหนด -> val <=left.maxVal แล้ว −

    • ผลตอบแทนสกุลเงิน

  • ถ้า left.ok ไม่ใช่ศูนย์ และ right.ok ไม่ใช่ศูนย์ ดังนั้น −

    • curr.sum :=val + left.sum + right.sum ของโหนด

    • ret :=สูงสุดของ curr.sum และ ret

    • curr.sz :=1 + left.sz + right.sz

    • curr.ok :=จริง

    • curr.maxVal :=สูงสุดของค่าโหนดและ right.maxVal

    • curr.minVal :=สูงสุดของค่าโหนดและ left.minVal

  • ผลตอบแทนสกุลเงิน

  • จากวิธีหลักให้ทำดังนี้

  • ยกเลิก :=0

  • แก้(ราก)

  • รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   } return root;
}
struct Data{
   int sz;
   int maxVal;
   int minVal;
   bool ok;
   int sum;
   Data(){}
   Data(int a, int b, int c, bool d){
      sz = a;
      minVal = b;
      maxVal = c;
      ok = d;
      sum = 0;
   }
};
class Solution {
   public:
   int ret = 0;
   Data solve(TreeNode* node){
      if (!node || node->val == 0)
      return Data(0, INT_MAX, INT_MIN, true);
      Data left = solve(node->left);
      Data right = solve(node->right);
      Data curr;
      curr.ok = false;
      if (node->val >= right.minVal) {
         return curr;
      }
      if (node->val <= left.maxVal) {
         return curr;
      }
      if (left.ok && right.ok) {
         curr.sum = node->val + left.sum + right.sum;
         ret = max(curr.sum, ret);
         curr.sz = 1 + left.sz + right.sz;
         curr.ok = true;
         curr.maxVal = max(node->val, right.maxVal);
         curr.minVal = min(node->val, left.minVal);
      }
      return curr;
   }
   int maxSumBST(TreeNode* root){
      ret = 0;
      solve(root);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v =
   {1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6};
   TreeNode *root = make_tree(v);
   cout << (ob.maxSumBST(root));
}

อินพุต

{1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}

ผลลัพธ์

20