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

有一个树结构，例如。

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

以及节点集（叶），必须在子树中，例如。

[5, 6]

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

   1
    \
     \
      3
     / \
    /   \
   5     6

最佳答案

基本上，您可以递归到叶子，并找到每个叶子，无论是否需要。当递归再次返回时，可以看到是否需要任何子代。
下面是执行此操作的伪代码：

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是基于哈希的字典，树中节点的复杂度是线性的。