最小子树包含来自给定节点集的节点

Question

有一个树形结构，例如：

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

节点（叶子）的集合，必须在子树中，例如：

[5, 6]

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

   1
    \
     \
      3
     / \
    /   \
   5     6

- mankers

---

树是否总是平衡的？ - User_Targaryen

@User_Targaryen 是的，没错。 - mankers

一个节点的值是否可以出现在树的多个位置？ - j_random_hacker

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是基于哈希表的字典，其复杂度与树中节点数量成线性关系。

- Ami Tavory

Answer 2

我认为没有必要遍历整棵树。我们只需要从每个给定的叶节点向根绘制连线即可。

类似这样的操作：

1. 将根节点标记为所需。
2. 选择第一个未处理的叶节点。如果没有，则完成操作。
3. 将当前节点标记为所需。
4. 转到当前节点的父节点。
5. 如果当前节点已被标记为所需，则转到步骤2，否则转到步骤3。

- Tymur Gubayev

Answer 3

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

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

您可以首先以线性时间预处理您的树，以便能够在常数时间内确定一对节点的最低公共祖先。然后，对于给定的查询，您可以找到两个查询节点的最低公共祖先，然后找到该节点和查询中第三个节点的最低公共祖先等，以在总体上O(k)时间内确定查询集中所有节点的最低公共祖先。但是，预处理和查询都很复杂，除非您的树与查询大小相比非常巨大并且您在同一棵树上有许多单独的查询（因此预处理所花费的时间得到回报），否则这不太可能是最快的方法。

- j_random_hacker