查找BST中的所有子树,其键位于给定范围内

Question

我在最近的一次采访中得到了这个问题:给定一个BST,其节点包含一个Integer作为值,找到其节点落在整数X(min)和Y(max)之间的所有子树,其中X <Y.这些子树不能相互重叠.

我已经解决了这个问题的变化,例如 - 打印在给定范围内的BST的键.但无法弄清楚这一点,因为它涉及查找满足非常特定约束的主图/树的所有连通子图.任何指针/帮助/伪代码都很受欢迎.

补充说明 -

1. 该问题将节点的数据结构定义为具有左指针,右指针和整数值.没有办法标记节点.
2. 有人要求用Java解决这个问题.
3. 当我说子树/子图时,我的意思是一组连接的节点,而不是一个不相交的节点列表.对困惑感到抱歉.

Answer 1

具体解决方案取决于子树的定义。考虑以下 BST：

5
  3
    2
    4
  8
    -
    9

我们想要找到范围内的子树[4,8]。显然该4节点属于输出。但是另一半树呢？如果子树引用一个节点及其所有子节点，那么这就是整个结果。如果子树实际上是输入节点的子集，则节点5和8属于结果，但必须剥离它们与3和节点的连接。9

无论如何，以下算法可以处理这两种情况。预处理器定义WHOLE_SUBTREES定义子树是否是具有所有子项的完整子组件。

5
  3
    2
    4
  8
    -
    9

其思想如下：如果给定节点只有一个子树位于给定范围内，那么这一定是新子树的根。如果两者都在该范围内，则它们不是子树的根。相反，家长级别应该处理相应的决定。

该算法从以下内容开始：我们遍历树并记住键可能在哪个范围内（treeRangeMin/Max）。这允许快速检查整个子树是否位于给定范围内（该IsTreeWithinRange方法的第一个语句。

接下来的两个语句处理当前节点的键位于给定范围之外的情况。那么只有它的子树之一可能在该范围内。如果是这种情况，则该子树将添加到结果列表中。

接下来，我们检查子树是否存在。如果两者都没有，则当前树完全包含在该范围内。

如果仅存在一棵子树，则操作会根据我们是否可以拆分树而有所不同。如果我们可以分割树，则会发生以下情况：如果子树不在范围内，我们将其切断并返回 true （因为当前节点包含在给定范围内）。如果我们不能分裂树，我们只需传播递归调用的结果。

最后，如果两个孩子都存在。如果其中之一不包含在该范围内，我们就会将其切断（如果允许的话）。如果不允许，我们会将子树添加到给定范围内的结果列表中。