java二进制搜索树差分键

Question

我昨天问了这个问题，但我仍然完全不知所措。我试图编写两个方法，一个包装器方法和一个名为sigma()的递归辅助方法，定义如下：

   /**
    * A wrapper method for a method that computes the
    * sum of the differential keys of this binary search tree.
    * @return the sum of the differential keys of this tree.
    */
   @Override
   public int sigma()
   {
       if (size == 0)
           return 0;
       if (root.data.getClass() != Integer.class)
           throw new IllegalArgumentException("Keys must be integers");
       return (Integer)root.data + sigma(root);
   }

   /** 
    * An auxiliary method that recursively computes the sum of
    * differential keys in the subtrees of the tree rooted at
    * the specified key.
    * @param subtreeRoot the root of a subtree of this tree
    * @return the sum of the differential keys of the left and
    * right subtrees
    */
   private int sigma(Node subtreeRoot)
   {
        // My attempt at implementing the auxiliary method
        if(subtreeRoot == null) return 0;
        return sigma(subtreeRoot.left) - (Integer)subtreeRoot.data + 
               sigma(subtreeRoot.right) - (Integer)subtreeRoot.data;
   }

注意：我们不允许向任一方法添加任何参数或修改包装器方法内部的代码

---

差分键的定义：

Definition 1. The differential key of a node in a binary tree whose elements are integers is the element in the node if the node is the root or is the difference between the element in the node and its parent. The differential of a null node is 0.

我已经讨论了基本情况，但之后我感到困惑。 下面是该方法应该做的一个示例：

辅助方法应该返回BST中所有差分键之和的值（本例中为-1），然后包装器方法将该值添加到根节点的值（本例中为10）。所以微分键和sigma（）返回的值之和是10+（-1）=9

我面临的主要问题是在辅助方法中实现递归解决方案。我可以很容易地在纸上找到解决方案，但我似乎无法在我的项目中实现这一点。我在网上找不到任何关于这方面的资源，我的教授也帮不了什么忙。上面的代码中包含了我实现辅助方法的尝试。感谢您的帮助