C++の二分木の最大合計BST

二分木ルートがあるとすると、二分探索木（BST）でもあるサブツリーのすべてのノードの最大合計を見つける必要があります。

したがって、入力が次のような場合、

その場合、出力は20になります。これは、選択したBST内のすべてのノードの合計です。

これを解決するには、次の手順に従います-

• Dataという1つのブロックを作成します。これには、sz、maxVal、minVal、ok、sumなどのメンバーが含まれます。また、この順序で取得するデータ用の初期化子を1つ定義します（sz、minVal、maxVal、ok、合計を0に設定）

• ret：=0

• ソルブ（）と呼ばれるメソッドを定義します。これはツリールートを取ります

• ノードがゼロ以外であるか、ノードの値が0と同じである場合、-

  • （0、inf、-inf、true）で初期化して新しいデータを返します

• 左：=solve（ノードの左側）

• 右=解決（ノードの右）

• currとい​​うデータ型インスタンスを1つ作成します

• curr.ok：=false

• node-> val> =right.minValの場合、-

  • リターンカー

• node-> 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：=true

  • curr.maxVal：=ノード値とright.maxValの最大値

  • curr.minVal：=ノード値とleft.minValの最大値

• リターンカー

• メインの方法から次のようにします

• ret：=0

• 解決（ルート）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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