C++에서 이진 트리의 최대 합 BST

<시간/>

이진 트리 루트가 있다고 가정하고 BST(Binary Search Tree)이기도 한 하위 트리의 모든 노드의 최대 합을 찾아야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 20이 됩니다. 이것은 선택된 BST에 있는 모든 노드의 합입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

Data라는 블록 하나를 생성합니다. 여기에는 sz, maxVal, minVal, ok, sum과 같은 일부 멤버가 포함됩니다. 또한 이 순서(sz, minVal, maxVal, ok 및 합계를 0으로 설정)를 취하는 데이터에 대한 하나의 초기화 프로그램을 정의합니다.
렛 :=0
solve()라는 메서드를 정의하면 트리 루트가 사용됩니다.
노드가 0이 아니거나 노드의 값이 0과 같으면 -
- (0, inf, -inf, true)로 초기화하여 새 데이터를 반환합니다.
왼쪽 :=해결(노드 왼쪽)
right =해결(노드 오른쪽)
curr이라는 데이터 유형 인스턴스를 하나 생성
curr.ok :=거짓
노드 -> val>=right.minVal이면 -
- 통화 반환
노드 -> val <=left.maxVal이면 -
- 통화 반환
left.ok가 0이 아니고 right.ok가 0이 아니면 -
- 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}