algorithm - 选择恰好包含 K 个叶子的子树

Question

我得到一棵T有n节点和l叶子的树。

我必须选择一些包含完全k (<=l)叶子的子树。如果我选择节点t'祖先'子树，我们不能选择t'子树。

例如：

这是T具有 13 个节点（7 个叶子）的树。

如果我想选择k = 4叶子，我可以选择节点 4 和 6（或节点 2 和 5）。这是选择的最小数量。（我们也可以选择节点 6、7、8、9，但这不是最小值）。

如果我想选择k = 5叶子，我可以选择节点3，这是选择的最小数量。

我想选择最小数量的子树。我只能找到使用 BFS 和动态编程的算法O(nk^2)。O(nk)选择这个有更好的解决方案吗？

谢谢 ：）

Answer 1

实际上，要知道每个子树的叶子数，您只需要遍历每个节点一次，因此复杂性应该是O(nm)每个m节点的平均子节点数，在大多数情况下计算结果为，O(n)因为m它只是一个常数。为此，您应该：

• 查找树的哪些节点是叶子
• 上树，为每个节点保存其子树中的叶子数

您可以通过从叶子开始并将父母放入队列中来做到这一点。当您n_i从队列中弹出一个节点时，将每个子树中包含的叶子数相加，从每个子树开始n_i。完成后，标记n_i为已访问（因此您不会多次访问，因为每个孩子可以添加一次）

这给出了这样的结果：

^
|               f (3)              This node last
|              / \
|            /     \
|          /         \
|        /             \
|       d (2)           e (1)      These nodes second
|      /  \            /
|     /    \          / 
|    a (1)  b (1)    c (1)         These nodes first

步骤是：

Find leaves `a`, `b` and `c`.
For each leave, add parent to queue   # queue q = (d, d, e)

Pop d                                 # queue q = (d, e)
Count leaves in subtree: d.leaves = a.leaves + b.leaves
Mark d as visited
Add parent to queue                   # queue q = (d, e, f)

Pop d                                 # queue q = (e, f)
d is visited, do nothing

Pop e                                 # queue q = (f)
Count leaves in subtree: e.leaves = c.leaves
Mark d as visited
Add parent to tree                    # queue q = (f, f)

Pop f                                 # queue q = (f)
Count leaves in subtree: f.leaves = d.leaves + e.leaves
Mark d as visited
Add parent to tree (none)

Pop f                                 # queue q = ()
f is visited, do nothing

您还可以使用将忽略添加两次的节点的智能数据结构。请注意，您不能使用有序集，因为在“较高”节点之前探索“较低”节点非常重要。

在您的情况下，如果队列中的节点超过k叶子，您可以消除它们，并返回您发现有k叶子的每个节点，这将提供更快的算法。