Tổng số tối đa BST trong Cây nhị phân trong C ++

Giả sử chúng ta có gốc cây nhị phân, chúng ta phải tìm tổng tối đa của tất cả các nút của bất kỳ cây con nào cũng là Cây tìm kiếm nhị phân (BST).

Vì vậy, nếu đầu vào giống như,

thì đầu ra sẽ là 20, đây là tổng của tất cả các nút trong BST đã chọn.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Tạo một khối có tên là Dữ liệu, khối này sẽ chứa một số thành viên như sz, maxVal, minVal, ok, sum. Cũng xác định một bộ khởi tạo cho dữ liệu, sẽ theo thứ tự này (sz, minVal, maxVal, ok và đặt tổng là 0)
ret:=0
Xác định một phương thức có tên là giải quyết (), phương thức này sẽ lấy gốc cây
nếu không phải nút khác 0 hoặc giá trị của nút bằng 0, thì -
- trả về một dữ liệu mới với việc khởi tạo nó bằng (0, inf, -inf, true)
left:=giải quyết (bên trái của nút)
right =giải quyết (bên phải của nút)
Tạo một phiên bản Kiểu dữ liệu được gọi là curr
curr.ok:=false
if node -> val> =right.minVal, then -
- trả lại curr
nếu nút -> val <=left.maxVal, thì -
- trả lại curr
nếu left.ok khác 0 và right.ok khác 0 thì -
- curr.sum:=val + left.sum + right.sum của nút
- ret:=tối đa của curr.sum và ret
- curr.sz:=1 + left.sz + right.sz
- curr.ok:=true
- curr.maxVal:=tối đa của giá trị nút và right.maxVal
- curr.minVal:=tối đa của giá trị nút và left.minVal
trả lại curr
Từ phương thức chính, hãy làm như sau
ret:=0
giải quyết (root)
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Tổng số tối đa BST trong Cây nhị phân trong C ++

Ví dụ

Đầu vào

Đầu ra