包含集合中节点的最小子树

Question

有一个树形结构，例如

   1
  / \
 /   \
2     3
|    / \
|   /   \
4  5     6

和一组节点（叶子），必须在子树中，例如

[5, 6]

如何找到包含所有这些节点并从根元素开始的最小子树？像这样：

   1
    \
     \
      3
     / \
    /   \
   5     6

Answer 1

基本上，您可以向下递归到叶子，并为每个叶子查找是否需要它。当递归再次返回时，您可以查看是否需要任何后代。

这是执行此操作的伪代码：

def mark_needed_nodes(node, given_nodes):
    # If a leaf, check if it is in given_nodes
    if node is leaf:
        node.needed = node in given_nodes
        return node.needed

    # It is not a leaf; check if any of the descendants is needed.
    node.needed = False
    for child in node.children:
        node.needed = needed or mark_needed_nodes(child, given_nodes)
    return node.needed

你会打电话给mark_needed_nodes(root, given_nodes)。

---

假设given_nodes是一个基于散列的字典，复杂度与树中的节点数呈线性关系。

Answer 2

我觉得，没必要遍历整棵树。我们可以 "draw the lines" 从每个给定的叶节点到根节点。

像这样：

1. 根据需要标记根节点。
2. 取第一个未处理的给定叶节点。如果有none，我们就完成了。
3. 标记当前需要的节点。
4. 转到当前节点的父节点。
5. 如果当前节点已经被需要，转到2，否则转到3。

Answer 3

假设您的查询集中有 k 个节点，树中有 n 个节点。如果您需要对同一棵树执行许多查询，并且该树比典型的查询集大得多，那么您可以考虑以下解决方案。

复杂的 O(n) 预处理时间、O(k) 查询时间解决方案

你可以先preprocess your tree in linear time so that you can determine the lowest common ancestor of a pair of nodes in constant time。然后，对于给定的查询，您可以找到两个查询节点的最低共同祖先，然后是该节点的最低共同祖先和查询中的第三个节点，依此类推，以确定您的所有节点的最低共同祖先查询集总时间为 O(k)。然而，预处理和查询都很复杂，这不太可能是最快的方法，除非你的树与你的查询大小相比很大，并且你在同一棵树上有许多单独的查询（这样花在预处理上的时间就会得到回报）。