주어진 이진 검색 트리에서 더 큰 값을 모두 각 노드에 추가합니다.

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

BST 문제 설명의 각 노드에 더 큰 값의 노드를 모두 추가합니다.

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

Input

    10
    /  \
   /    \
  5     20
 / \   / \
1   7   1  5

Output

      70
    /   \
   82   45
  / \   / \
83 77  60 25

Explanation

이 프로그램은 이진 검색 트리를 노드의 값이 모든 더 큰 요소의 합과 노드의 원래 값을 더한 이진 트리로 변환합니다.

이진 검색 트리 솔루션의 각 노드에 더 큰 값을 모두 추가합니다.

우리는 역중위 순회(왼쪽 하위 트리 대신 오른쪽 하위 트리를 먼저 재귀적으로 호출)를 사용하고 변수를 유지하여 저장합니다. 지금까지 횡단했습니다.

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

예

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

위 내용은 주어진 이진 검색 트리에서 더 큰 값을 모두 각 노드에 추가합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!