algorithm - 使用图遍历来测试图是否是完美二叉树

Question

当给定一个由邻接表表示的无向图 G 时，如何使用 DFS 来查看该图是否是完美二叉树？

我已经能够识别边缘情况:例如，对于深度 D，您需要 2^n-1 个节点，您可以使用对数计算出最大深度，如果这不是完整的，您知道你没有完美的树，但我想不出使用邻接表和 DFS 进行测试的有效方法。

Answer 1

在一棵非空的完美二叉树中，有 𝑛 节点，我们有以下属性:

• 节点数 𝑛 为 2 的幂减一，即 ℎ=log₂(𝑛+1) 为整数。 𝑛=2^ℎ−1
• 边的数量为 𝑛−1
• 不存在超过 3 个邻居的节点。
• 当 𝑛 > 1 时，(仅)有一个节点恰好有 2 个邻居:它是根。
• 当 𝑛 > 1 时，树上的叶子只有一个邻居:有 2^ℎ-1 个。
• 根与任意叶子之间的距离为ℎ−1。

这些属性可以依次检查。一旦确定了根，就可以执行遍历来检查距离属性。使用 DFS 或 BFS。