二叉树的最小顶点覆盖
Minimum vertex cover of a binary tree
如果你有一个有 2^n - 1 个顶点的二叉树，其中 n >= 1，需要多少个顶点才能达到最小顶点覆盖？
假设我们有 L 个级别（1 到 L），其中 (n = 2^L - 1)。解决方案是先选取 L-1 层的所有节点，然后是 L-3 层的所有节点，依此类推。然而，我们停止取决于 n 是奇数还是偶数。如果 n 是奇数，我们在第 1 级停止，如果它是偶数，我们在第 2 级停止。这可以通过强归纳法证明（如何？）。
如果你有一个有 2^n - 1 个顶点的二叉树，其中 n >= 1，需要多少个顶点才能达到最小顶点覆盖？
假设我们有 L 个级别（1 到 L），其中 (n = 2^L - 1)。解决方案是先选取 L-1 层的所有节点，然后是 L-3 层的所有节点，依此类推。然而，我们停止取决于 n 是奇数还是偶数。如果 n 是奇数，我们在第 1 级停止，如果它是偶数，我们在第 2 级停止。这可以通过强归纳法证明（如何？）。