algorithm - 二叉树的最小顶点覆盖

Question

如果您有一个包含 2^n - 1 个顶点的二叉树，其中 n >= 1，那么要达到最小顶点覆盖率所需的顶点数量是多少？

Answer 1

假设我们有 L 个级别(1 到 L)，其中 (n = 2^L - 1)。解决方案是先选取 L-1 层的所有节点，然后是 L-3 层的所有节点，依此类推。然而，我们停止取决于 n 是奇数还是偶数。如果 n 是奇数，我们在级别 1 停止，如果它是偶数，我们在级别 2 停止。这可以通过强归纳法证明(如何？)。