BST或二叉搜索树是一种二叉树形式，其中所有左节点的值小于根节点的值，所有右节点的值大于根节点的值。对于这个问题，我们将取一个二叉树并将所有大于当前节点值的值添加到它中。问题“向BST的每个节点添加所有较大的值”被简化为对于BST，将所有大于当前节点值的节点值添加到该节点值。
向BST中的每个节点添加所有较大的值问题陈述：
给定一个二叉搜索树（BST），我们需要为每个节点添加所有较大值节点的总和。
输入
10 / / 5 20 / / 1 7 1 5
输出
70 / 82 45 / / 83 77 60 25
解释
这个程序将把一个二叉搜索树转换为一个二叉树，其中节点的值为所有较大元素的和加上节点的原始值。
将所有较大的值添加到二叉搜索树解决方案中的每个节点：
我们使用逆向中序遍历（先递归调用右子树而不是左子树），并维护一个变量来存储到目前为止已经遍历过的节点的和。
然后，我们使用这个和来修改当前节点的值，首先将其值加到和上，然后用这个和替换节点的值。
示例
#include 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<data<right);}node *Insert(node *root,int key) { if(!root) return newNode(key); if(keydata) 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;}
以上就是将给定二叉搜索树中的所有较大值添加到每个节点上的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444557.html
微信扫一扫 
支付宝扫一扫 
