C++에서 주어진 BST의 모든 노드에 더 큰 값을 모두 추가하시겠습니까?

BST 또는 이진 탐색 트리는 모든 왼쪽 노드가 루트 값보다 작고 오른쪽 노드가 모두 큰 이진 트리의 한 형태입니다. 이 문제의 경우 이진 트리를 가져와 현재 노드보다 큰 모든 값을 여기에 추가합니다. BST가 현재 노드 값보다 큰 모든 노드 값을 해당 노드 값에 추가하는 것처럼 "모든 더 큰 값을 BST의 모든 노드에 추가" 문제는 단순화됩니다.

BST 문제 설명의 각 노드에 더 큰 모든 값 추가 -

이진 검색 트리(BST)가 주어지면 각 노드에 더 큰 값 노드의 합계를 추가해야 합니다.

설명

이 프로그램은 BST를 모든 더 큰 요소와 노드의 원래 값의 합으로 노드 값을 갖는 이진 트리로 변환합니다.

이진 검색 트리 솔루션의 각 노드에 더 큰 모든 값 추가 -

Reverse Inorder Traversal(재귀는 왼쪽 하위 트리가 아닌 오른쪽 하위 트리에서 먼저 호출됨)을 사용하고 지금까지 순회한 노드의 합계를 저장하는 변수를 유지합니다.

그런 다음 이 합계를 사용하여 현재 노드의 값을 수정합니다. 먼저 해당 값을 합계에 추가한 다음 노드 값을 이 합계로 대체합니다.

예시

#include <iostream >
using namespace std;
struct node{
   int data;
   node *left;
   node *right;
};
node *newNode(int key){
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}
void Inorder(node *root){
   if(!root)
   return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}
node *Insert(node *root,int key){
   if(!root)
   return newNode(key);
   if(key<root->data)
      root->left=Insert(root->left,key);
   else
      root->right=Insert(root->right,key);
   return root;
}
void RevInorderAdd(node *root,int &sum){
   if(!root)
   return;
   RevInorderAdd(root->right,sum);
   sum+=root->data;
   root->data=sum;
   RevInorderAdd(root->left,sum);
}
void AddGreater(node *root){
   int sum=0;
   RevInorderAdd(root,sum);
}
int main() {
   /* Let us create following BST
   10
   / \
   5 20
   / \ / \
   1 7 15 25 */
   node *root = NULL;
   root = Insert(root, 10);
   Insert(root, 20);
   Insert(root, 25);
   Insert(root, 15);
   Insert(root, 5);
   Insert(root, 7);
   Insert(root, 1);
   Inorder(root);
   cout<<endl;
   AddGreater(root);
   Inorder(root);
   cout<<endl;
   return 0;
}