algorithm - 从树中选择 K 个节点的方法数，如果选择节点，则必须选择节点的父节点

Question

我正在尝试解决这个问题，我有一棵树，其中每个节点都可以有任意数量的子节点。我必须找到所有可能的方法来选择 K 个节点，以便只有在选择父节点时才会选择任何节点。

我试过了，但找不到解决方案。有人能帮助我吗？基本算法(伪代码)就够了。

Answer 1

我们可以用DFS来解决这个问题。将每个可能的选择视为图的一个顶点。如果我们可以通过从选择中删除一个顶点并将另一个有效的树节点添加到选择中，将一个选择转换为另一个选择，则两个顶点/选择之间将相应地存在一条边。这个图是连通的，所以我们可以用DFS遍历它。

例如:

input tree:       1              K=3
               /  |  \
              3   4   5
                /   /   \
               6   7     2

first solution (preorder traversal):
         1
      /  |
     3   4

consecutive solutions:
    removing node 3 from selection   removing node 4
         1         1                       1
         |         |  \                  /   \
         4         4   5                3     5
       /
      6

因为我们需要一个起始顶点来生成其他顶点，所以我们需要一个有效的选择作为开始。最简单的解决方案是遍历树预序并选择前 K 节点。

从那个起始顶点，我们可以在运行中生成整个图:
基本上每个节点都包含来自输​​入树的子树，也就是选择。从您刚刚遍历的节点中进行选择。通过从选择表示的子树中删除任意叶子，我们获得了一个具有 K - 1 节点的子树/选择。此选择可以完成到 K 个节点，方法是将另一个节点添加到将成为新叶子的子树中。这种方法也符合上面给出的边的定义。

所以现在我们知道如何从给定的顶点/选择生成所有相邻的顶点。剩下的只是一个普通的 DFS 遍历。将顶点标记为已访问，获取所有相邻顶点，并对它们执行 DFS 遍历，直到所有顶点都已访问。