查找BST中的所有子树，其键位于给定范围内-Java 学习之路

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

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

补充说明 -

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

4 回答

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

我们希望找到 [4,8] 范围内的子树 . 很明显， 4 节点属于输出 . 但另一半树怎么样？如果子树引用具有其所有子节点的节点，那么这就是整个结果 . 如果子树实际上是输入节点的子集，则节点 5 和 8 属于结果，但是它们与 3 和 9 节点的连接必须被剥离 .

在任何情况下，以下算法都可以处理这两种情况 . 预处理器定义 WHOLE_SUBTREES 定义子树是否是包含所有子节点的整个子组件 .

static List<BSTNode> FindSubtreesInRange(BSTNode root, int rangeMin, int rangeMax)
{
    var result = new List<BSTNode>();
    if (IsTreeWithinRange(root, rangeMin, rangeMax, int.MinValue, int.MaxValue, result))
        result.Add(root);
    return result;
}

static bool IsTreeWithinRange(BSTNode root, int rangeMin, int rangeMax, int treeRangeMin, int treeRangeMax, List<BSTNode> resultList)
{
    if (treeRangeMin >= rangeMin && treeRangeMax <= rangeMax)
        return true;
    if ( treeRangeMin > rangeMax || treeRangeMax < rangeMin)
        return false;

    if (root.Key < rangeMin)
    {
        if (root.Right != null && IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList))
            resultList.Add(root.Right);
        return false;
    }

    if (root.Key > rangeMax)
    {
        if (root.Left != null && IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList))
            resultList.Add(root.Left);
        return false;
    }

    if (root.Left == null && root.Right == null)
        return true;

    if (root.Left == null)
    {
#if WHOLE_SUBTREES
        if (!IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList))
            root.Right = null;
        return true;
#else
        return IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList);
#endif
    }

    if (root.Right == null)
    {
#if WHOLE_SUBTREES
        if (!IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList))
            root.Left = null;
        return true;
#else
        return IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList);
#endif
    }

    var leftInRange = IsTreeWithinRange(root.Left, rangeMin, rangeMax, treeRangeMin, root.Key, resultList);
    var rightInRange = IsTreeWithinRange(root.Right, rangeMin, rangeMax, root.Key + 1, treeRangeMax, resultList);

    if (leftInRange && rightInRange)
        return true;

#if WHOLE_SUBTREES
    if (!leftInRange)
        root.Left = null;
    if (!rightInRange)
        root.Right = null;
    return true;   
#else
    if (leftInRange)
        resultList.Add(root.Left);
    if (rightInRange)
        resultList.Add(root.Right);
    return false;
#endif

}

这个想法如下：如果给定节点中只有一个子树位于给定范围内，那么它必须是新子树的根 . 如果两者都在范围内，那么它们不是子树的根 . 相反，父级别应该处理相应的决定 .

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

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

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

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

最后，如果两个孩子都存在 . 如果其中一个未包含在范围内，我们将其剪掉（如果允许的话） . 如果我们不被允许，我们将子树添加到位于给定范围内的结果列表中 .

回复于 2024-04-29T15:11:22+08:00

解决这个问题非常简单 . 对于不重叠的子树，我包括一个标记字段，每个节点初始化为false .

算法如下：

使用DFS方法从root开始遍历BST . 现在，如果在DFS中遇到一个节点，它没有被标记并且它满足约束（在X和Y之间），则有一个以该节点为根的子树的解决方案，但我们不知道该子树有多大？所以我们做了以下事情：

将其左右孩子传递给另一个方法检查，这将执行以下操作：

遍历以节点为根的子树，并以DFS方式遍历它，只要满足约束并且遇到的节点未标记 . 一旦违反任何一个条件，就返回 .

现在，可以在已标记的顶点上调用原始DFS方法，但if条件将评估为false . 因此实现了目标 .

我使用JAVA语言解决了它，并且条件是键位于10到21之间（不包括） . 这是代码：

还有一件事，如果在 subtree rooted at X with childs as 之后没有打印，那么它表示具有单个节点的子树 .

class BST
{
 public Node insert(Node x,int key)
 {
     if(x==null)
      return new Node(key,null,null,false);
     else if(key>x.key)
     {
         x.right=insert(x.right,key);
         return x;
     }
     else if(key<x.key)
     {
         x.left=insert(x.left,key);
         return x;
     }
     else {x.key=key;return x;}
 }

 public void DFS(Node x)
 {
     if(x==null)
     return;
     if(x.marked==false&&x.key<21&&x.key>10)
     {
         System.out.println("Subtree rooted at "+x.key+" with childs as");
         x.marked=true;
         check(x.left);
         check(x.right);
     }
     DFS(x.left);
     DFS(x.right);

 }
 public void check(Node ch)
 {
     if(ch==null)
      return;
     if(ch.marked==false&&ch.key<21&&ch.key>10)
     {
         System.out.println(ch.key);
         ch.marked=true;
         check(ch.left);
         check(ch.right);
     }
     else return;

 }
 public static void main(String []args)
 {
     BST tree1=new BST();
     Node root=null;
     root=tree1.insert(root,14);
     root=tree1.insert(root,16);
     root=tree1.insert(root,5);
     root=tree1.insert(root,3);
     root=tree1.insert(root,12);
     root=tree1.insert(root,10);
     root=tree1.insert(root,13);
     root=tree1.insert(root,20);
     root=tree1.insert(root,18);
     root=tree1.insert(root,23);   
     root=tree1.insert(root,15);
     tree1.DFS(root);
 } 
}
class Node
{
 Node left,right;
 int key;
 boolean marked;
 Node(int key,Node left,Node right,boolean b)
 {
  b=false;   
  this.key=key;
  this.left=left;
  this.right=right;
 }
}

如有任何疑问，请随意 .

回复于 2024-04-29T15:11:22+08:00

1
这可以递归地完成，并且我们保留一个子树列表，只要找到一个兼容的子树，我们就会附加这些子树 . 当以参数节点为根的子树完全在范围内时，递归函数返回true . 这是来电者的决定（父节点）确定当孩子的recusruve调用返回true或false时要执行的操作 . 例如，如果当前节点值在范围内，并且其子节点的子树也完全在范围内，那么我们只返回true . 但是，如果只有一个子树的子树在范围内，而另一个不在范围内，那么我们返回false（因为并非所有当前节点子树都在范围内），但我们还附加了列表的范围 . 如果当前节点值不在我们返回false的范围内，但我们也检查左子项或右子项，如果它符合要求，则将其附加到子树列表中：
```
def subtree_in_range(root, x, y):
  def _subtree_in_range(node):
    in_range=True
    if node:
      if node.val>=x and node.val<=y:
        if not _subtree_in_range(node.left):
          in_range=False
          if node.right and _subtree_in_range(node.right):
            l.append(node.right)
        elif not _subtree_in_range(node.right):
          in_range=False
          if node.left:
            l.append(node.left)
      else:
        in_range=False
        s=node.left
        if node.val<x:
          s=node.right
        if s and _subtree_in_range(s):
          l.append(s)
    return in_range

  l=[]
  if _subtree_in_range(root):
    l.append(root)
  return l
```
回复于 2024-04-29T15:11:22+08:00

在进行范围搜索时，使用某种通用语言编写的范围的主力函数可能是这样的：

function range(node, results, X, Y) 
{
    if node is null then return
    if node.key is in [X, Y] then results.add(node.key)
    if node.key < Y then range(node.right, results, X, Y)
    if node.key > X then range(node.left, results, X, Y)
}

对于子树版本问题，我们需要存储子树根节点而不是键，并且如果我们在子树中，则保持跟踪 . 后者可以通过在范围调用中传递子树智能父来解决，这也是新结构创建所必需的 . 所需功能如下 . 如您所见，主要变化是一个额外的参数和 node.key in [X, Y] 分支

function range_subtrees(node, parent, results, X, Y) 
{
    if node is null then return

    node_clone = null 

    if node.key is in [X, Y] then 
        node_clone = node.clone()
        if parent is null then 
            results.add(node_clone)
        else
            parent.add_child(node_clone)

    if node.key < Y then range_subtrees(node.right, node_clone, results, X, Y)
    if node.key > X then range_subtrees(node.left, node_clone, results, X, Y)
}

这应该创建一个子树根节点的集合，其中每个子树是原始树结构的副本 .

回复于 2024-04-29T15:11:22+08:00

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

4 回答

相关问题