BST 또는 이진 검색 트리는 모든 왼쪽 노드가 루트 값보다 작고 오른쪽 노드가 모두 큰 이진 트리의 한 형태입니다. 이 문제의 경우 이진 트리를 가져와 현재 노드보다 큰 모든 값을 여기에 추가합니다. BST가 현재 노드 값보다 큰 모든 노드 값을 해당 노드 값에 추가하는 것처럼 "모든 더 큰 값을 BST의 모든 노드에 추가" 문제는 단순화됩니다.
BST 문제 설명의 각 노드에 더 큰 값을 모두 추가합니다.
BST(Binary Search Tree)가 주어지면 모든 더 큰 값 노드의 합계를 각 노드에 추가해야 합니다.
입력
10 / \ / \ 5 20 / \ / \ 1 7 1 5
출력
70 / \ 82 45 / \ / \ 83 77 60 25
설명
이 프로그램은 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;
}