BST :将每个键值按所有其他较大键的总和递增

Question

>问题陈述：给定一个二叉搜索树（BST），将其转换为二叉树，这样原始BST的每个键都更改为BST中所有更大键的键加上总和。

Input:  BST
              5
            /   
           2     13
                /  
               11  14
Output: The given BST is converted to following Binary Tree
              43
             /  
            45   27
                /  
               38   14

我能够在网上挖掘出这段有效的代码，但我无法真正掌握它。传递一个变量来维持到目前为止的先前总和进一步使我的理解复杂化。

请注意解释，以更好地解释。或者使下面的代码更直观。

public class BSTWithInts
{
    private Node root;
    private class Node
    {
        Node leftChild;
        Integer item;
        Node rightChild;
    }
    public void addsNodes()
    {
        addSumUtil(root, 0);
    }

    private int addSumUtil(Node node, int sum)
    {
        if(node == null)
            return 0;
        if ( node.rightChild != null )
        {
            sum = addSumUtil(node.rightChild, sum);
        }
        if ( node.leftChild != null )   
        {
            sum = addSumUtil(node.leftChild, sum);
            // why are we doing this here, shouldn't we just 
            // traverse right tree only first
        }
       node.item += sum;
       sum = node.item;
       return sum;
    }
}

编辑：我刚刚意识到代码没有按照应有的方式工作。

              5             
            /   
           2     13
    should give 
             18
            /   
          20     13
    and not      
             20
            /   
          15    13

Answer 1

想象一下最简单的

方法，记住它是一个搜索树，所以一切都井井有条。 您希望从最高的数字开始。 记录下来，别管它。 然后是第二高的数字：将最高的数字加进去，并保留一份副本，因为这也是"高于第三高数字的所有数字的总和"。 将其添加到第 3 个最高数字并保留总和，因为它将添加到第 4 个最高数字。 您拖动该总和，每次将其增加当前数字（反之亦然）。 当你得到最小的数字时，你就得到了树的其余部分的总和，准备添加到它上面。

另外，我认为您找到的代码是错误的，即使它确实适用于示例树。 它应该看起来更像：

private int addSumUtil(Node node, int sum)
{
    if (node == null) {
        return sum;
    }
    sum = addSumUtil(node.rightChild, sum);
    sum = node.item += sum;
    sum = addSumUtil(node.leftChild, sum);
    return sum;
}

请注意，sum = addSumUtil(null, sum);是一个 noop。

Answer 2

要了解上述代码中发生了什么，您需要了解递归的工作原理。

开始理解这一点的简单方法是在处理中使用 System.out.println 语句，以便左右子项更好地理解正在发生的事情：

        if ( node.rightChild != null )
        {
            System.out.println("Accessing right child: "+node.rightChild.item);
            sum = addSumUtil(node.rightChild, sum);
        }
        if ( node.leftChild != null )   
        {
            System.out.println("Accessing left child: "+node.leftChild.item);
            sum = addSumUtil(node.leftChild, sum);
            // why are we doing this here, shouldn't we just 
            // traverse right tree only first
        }

您会发现 print 语句的输出按以下顺序排列，从而确认每个节点的右子节点在其左子节点之前被计算。

Accessing right child: 13
Accessing right child: 14
Accessing left child: 11
Accessing left child: 2