数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在给定的BST中，将所有更大的值添加到每个节点？
BST 或二叉搜索树是一种二叉树的形式，其中所有左节点都小于根值，所有右节点都大于根值。对于这个问题，我们将取一个二叉树，并将所有大于当前节点的值添加到它。问题“将所有大于每个节点的值添加到BST中”简化为对于BST，将所有大于当前节点值节点的值添加到该节点值。
在BST中将所有更大的值添加到每个节点问题陈述
给定一个二叉搜索树 (BST)，我们需要将所有大于当前节点的值之和添加到每个节点中。
输入
10 / \ / \ 5 20 / \ / \ 1 7 1 5
输出
70 / \ 82 45 / \ / \ 83 77 60 25
解释
此程序将把BST转换为二叉树，节点的值为所有大于元素的总和加上节点的原始值。
在二叉搜索树中将所有更大的值添加到每个节点的解决方案
我们使用逆序遍历（递归首先调用右子树而不是左子树）并维护一个变量来存储到目前为止已遍历的节点的总和。
然后，我们使用此总和修改当前节点的值，首先将它的值添加到总和中，然后用此总和替换节点的值。
示例
#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;
}
更新于: 2020年7月1日
200 次浏览
广告