在 BST 的半路径中按键值节点求平均值

Question

描述：

是否有可能在 BST 的半路径中找到关键节点的平均值，只知道它的根、长度和最后节点的键的总和？

例子：

BST:
    0  <- Given root <------ 0
     \
      5
     / \
    2   6  
   /     \     
  1       7                  +    = 10 - Given Sum         
           \
            8
             \
              9
               \
               10    <------ 10

给定数据：

1)半路径的根（指向根的指针）：0

2)长度：6

3)最后一个节点的键值之和：10

• 这个半路径看起来像：0 - 5 - 6 - |7| - 8 - 9 - 10

• 按值节点的平均值为 7， 因为正好有 3 个节点大于键为 7 的节点 长度 = 6 时少 3 个。 （一些半路径的按值节点的平均值的定义）

想法：

由于sum和length不能唯一确定这个半路径，所以可能不止一个，这种情况下我们会找到所有可能的半路径的平均节点。

当然我们可以尝试重构这个半路径（可以不止一个）。为了找到 avg 节点，我们需要花费额外的时间（找到在给定半路径长度距离内且具有给定总和的所有可能顶点），然后在找到的路径中我们可以找到 O( n)，其中 n 是路径长度。

但是我不知道如何在树的一次遍历中找到具有如此有限输入数据集的节点。