用大于或等于该节点的节点之和替换BST节点。
提问于 2013-04-27 09:51:06
我想知道解决以下问题的算法：
给定一个BST(可能有重复的节点)，用值替换每个节点，该值是所有节点大于当前节点的值之和。
示例：
5 15 2 10 o/p: 17 10
我这样做的逆序遍历保持一个变量‘和’。以下是代码：
public static void replaceNodeValue(BSTNode root, int[] sum) {
if (root == null) return;
replaceNodeValue(root.right, sum);
root.data = (sum[0] = sum[0] + root.data);
replaceNodeValue(root.left, sum);
}问题是，只有在树不包含重复节点的情况下，此代码才能工作。我正在寻找正确的算法，这将处理重复的节点也。
代码将失败的一种情况是：
5 5 5
请帮帮忙。谢谢
回答 6
Stack Overflow用户
回答已采纳
发布于 2014-01-18 03:46:32
这是这个问题的O(n)解。访问每个节点和大于数的值，遍历每个node.Since的树，所有节点都需要访问树，复杂度为O(n)。
int sum_all(Node root)
{
if(root == null) return 0;
return root.data + sum_all(root.left) + sum_all(root.right);
}
void replace_keys(Node root, int total)
{
if(root == null) return;
int leftsum = sum_all(root.left);
root.data = (total - leftsum - root.data);
replace_keys(root.left, total);
replace_keys(root.right, total);
}
void replace_keys(Node root)
{
int total = sum_all(root);
replace_keys(root, total);
}Stack Overflow用户
发布于 2014-05-04 10:48:24
这个问题可以递归地解决，其背后的想法是：
对于BST中的任何节点：
- 右子树的所有元素都大于或等于父元素。
- 左子树的值小于父树。
有了这就是心灵
- 对于每个节点，我们将它的值替换为它的右子树+它自己的值之和。(我们递归地计算右子树之和:)
- 然后，我们去它的左子，并将它的值替换为它的父值+它自己的值+它是右子树的最大和。
当我们遇到没有正确子树的节点时，递归的终止条件就会发生。当发生这种情况时，节点的值将是它自己的值，然后返回。
C/C++ ish伪代码：
NODE* recSum(root){
getSum(root);
return root;
}
int getSum(NODE *n){
if (n->r == NULL) return n->val;
else{
n->val = getSUM(n->r) + n->val;
n->l->val = getSUM(n) + getSUM((n->l)->r);
}
}Stack Overflow用户
发布于 2013-04-27 10:16:01
首先，遍历BST并将每个节点推入数组中。
其次，对数组进行排序。
最后，再次遍历BST并在数组的帮助下进行替换。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16255186
复制
腾讯云开发者
