1

I would like to know the algorithm for the following problem:
"Given a BST(There can be duplicate nodes), replace every node with value which is sum of values of all nodes greater than equal to the current node."

Example:

                              5                15
                            2  10     o/p:   17  10

I did it with reverse in-order traversal keeping a variable 'sum'. Here is the code:

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

The problem is this code works only if the tree doesn't contain a duplicate node. I am looking for the correct algorithm which will handle duplicate nodes also.

One case for which the code will fail is:

                               5
                            5     5

Please help. Thanks

4

6 回答 6

2

这个问题可以递归解决，其背后的思想是：

对于 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);
    }
}
于 2014-05-04T18:48:24.450 回答
2

这是该问题的 O(n) 解决方案。通过遍历每个节点的树来访问每个节点和大于数字的值。由于需要为所有节点访问树，因此复杂度将为 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);
}
于 2014-01-18T11:46:32.727 回答
0

首先，遍历 BST 并将每个节点推入一个数组。

其次，对数组进行排序。

最后，再次遍历BST，在数组的帮助下进行替换。

于 2013-04-27T18:16:01.887 回答
0

算法：

逆序遍历，更新总和

这是java实现

public static void modifyWithSumOfGreaterNodes(BinaryTreeNode<Integer> bst) {
    doModifyWithSumOfGreaterNodes(bst, new MutableInteger(0));      
}

private static void doModifyWithSumOfGreaterNodes(BinaryTreeNode<Integer> bst, MutableInteger sum) {
    if (bst == null) {
        return ;
    }

    doModifyWithSumOfGreaterNodes(bst.getRight(), sum);
    sum.add(bst.getData());
    bst.setData(sum.getValue());
    doModifyWithSumOfGreaterNodes(bst.getLeft(), sum);      
}

这是单元测试

@Test
public void replaceBSTNodesWithSumOfNodesGreaterOrEqualToNodeTest() {

    BinaryTreeNode<Integer> eighty = new BinaryTreeNode<Integer>(80);
    BinaryTreeNode<Integer> sixty = new BinaryTreeNode<Integer>(60);
    BinaryTreeNode<Integer> forty = new BinaryTreeNode<Integer>(40);
    BinaryTreeNode<Integer> twenty = new BinaryTreeNode<Integer>(20);
    BinaryTreeNode<Integer> seventy = new BinaryTreeNode<Integer>(70, sixty, eighty);
    BinaryTreeNode<Integer> thrity = new BinaryTreeNode<Integer>(30, twenty, forty);
    BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(50, thrity, seventy);

    BinaryTreeUtil.modifyWithSumOfGreaterNodes(root);

    assertThat(BinaryTreeUtil.iPostOrder(root).toArray(new Integer[0]), equalTo(new Integer[]{350,300,330,210,80,150,260}));


}
于 2016-04-11T16:16:21.097 回答
0

这是java中的完整程序

BinarySearchTree 类定义

public class BST<T> {

public Node root;

 static class Node<T>{
 public Node left;  
 public Node right;
 public T data;

 Node(T data){
     this.data =data;
 }
}

}

实际的类定义，其中每个节点都替换为给定 BST 中所有更大节点的总和

public class TestGreaterNodeBST {



    public static void main(String[] args) {
        BST<Integer> bst = new BST<Integer>();
        bst.root= new BST.Node<Integer>(50);
        bst.root.left =new BST.Node<Integer>(30);
        bst.root.right =new BST.Node<Integer>(80);
        bst.root.right.left =new BST.Node<Integer>(70);
        bst.root.right.left.left =new BST.Node<Integer>(60);
        bst.root.right.right =new BST.Node<Integer>(100);
        bst.root.right.right.right =new BST.Node<Integer>(120);
        bst.root.right.right.right.left =new BST.Node<Integer>(110);
        bst.root.right.right.right.right =new BST.Node<Integer>(150);

        printInOrderDescending(bst.root);
        System.out.println();
        System.out.println();
        transformToGreaterNode(bst.root, 0);
        printInOrderDescending(bst.root);

    }


    static void printInOrderDescending(BST.Node node){

        if(node==null){
            return;
        }

        printInOrderDescending(node.right);
        System.out.println(node.data);
        printInOrderDescending(node.left);

    }



    static Integer transformToGreaterNode(BST.Node<Integer> node, Integer sum){

        if(node==null){
            return sum;
        }


        sum = transformToGreaterNode(node.right, sum);

        Integer data = node.data;
        node.data=sum;
        sum = sum + data;

        sum = transformToGreaterNode(node.left, sum);

        return sum;
    }

}
于 2016-10-08T11:15:28.140 回答
0

您需要有一个字段名称为 sum 的对象。随着您的进行，您将更新此总和。我的解决方案是递归的。考虑到我们处理的是有序树（二叉搜索树），需要先遍历右子节点，然后更新当前节点并求和。然后，遍历左孩子。到递归结束时，现有根将是大和树的根（每个节点都有大于或等于同一节点的节点的值的总和）。

/**
 * Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.
 * <p>
 * As a reminder, a binary search tree is a tree that satisfies these constraints:
 * <p>
 * The left subtree of a node contains only nodes with keys less than the node's key.
 * The right subtree of a node contains only nodes with keys greater than the node's key.
 * Both the left and right subtrees must also be binary search trees.
 * Reference: LeetCode
 */
public class BinarySearchTreeToGreaterSumTree {

    class Sum {
        public int sum = 0;
    }

    public static void main(String[] args) {
/*
public class TreeNode {

    Integer val;
    TreeNode left;
    TreeNode right;

    TreeNode(Integer x) {
        val = x;
    }

    TreeNode(TreeNode treeNode) {
        if (treeNode != null) {
            this.val = treeNode.val;
            this.left = new TreeNode(treeNode.left);
            this.right = new TreeNode(treeNode.right);
        }
    }

}
 */
        TreeNode node0 = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        node4.left = node1;
        node4.right = node6;
        node1.left = node0;
        node1.right = node2;
        node2.right = node3;
        node6.left = node5;
        node6.right = node7;
        node7.right = node8;

        BinarySearchTreeToGreaterSumTree bstToGST = new BinarySearchTreeToGreaterSumTree();
        // the input of this method should be the root of the tree
        TreeNode result = bstToGST.bstToGst(node4);
        System.out.println();
    }

    /**
     * Builds a GST.
     *
     * @param root The root of the binary search tree
     * @return The GST
     */
    public TreeNode bstToGst(TreeNode root) {
        if (root != null) {
            Sum sum = new Sum();
            buildGST(root, sum);
        }
        return root;
    }

    /**
     * A recursive method to build the Greater Sum Tree.
     *
     * @param currentNode The current node
     * @param sum         The current summation
     */
    private void buildGST(TreeNode currentNode, Sum sum) {
        if (currentNode == null)
            return;
        // Call build GST on the right child
        TreeNode r = currentNode.right;
        buildGST(r, sum);
        // Update the current sum with the value of the current node
        sum.sum = sum.sum + currentNode.val;
        // Update the value of the current node with the new sum
        currentNode.val = sum.sum;
        // Call build GST on the left child with the updated sum
        TreeNode l = currentNode.left;
        buildGST(l, sum);
    }

}

我希望它有所帮助。

于 2020-03-29T16:35:42.623 回答