如何利用深度优先搜索（DFS）判断邻接表表示的无向图是否为完美二叉树

Great catch on the node count check — that's a quick first filter to rule out most non-perfect binary trees right away! Let's break down how to combine that with DFS and adjacency list traversal to fully validate the structure.

核心思路回顾 #

完美二叉树的两个关键特性：

1. 总节点数必须是 2^D - 1，其中 D 是树的深度（层数，从1开始计数）。
2. 所有叶子节点在同一深度，且每个非叶子节点恰好有两个子节点。

对于无向图的邻接表表示，我们还可以利用节点度数的特性快速筛选：

• 根节点：度数为2（仅连接两个子节点，无父节点），除非是单节点树（度数为0）。
• 中间非叶子节点：度数为3（连接父节点+两个子节点）。
• 叶子节点：度数为1（仅连接父节点）。

分步验证流程 #

1. 初步节点数校验 #

先快速判断节点数是否符合完美二叉树的要求：

• 设总节点数为 n，计算 D = log2(n + 1)。
• 如果 D 不是整数，或者 n <= 0，直接返回 false。
• 特殊情况：当 n = 1 时，这是深度为1的完美二叉树，直接返回 true。

2. 节点度数校验 #

遍历所有节点的度数，快速排除结构异常的图：

• 统计度数为2的节点数量，必须恰好有1个（这是根节点）。
• 所有其他节点的度数只能是1（叶子）或3（中间非叶子），否则返回 false。

3. DFS遍历验证结构 #

以找到的根节点为起点，进行DFS遍历，同时跟踪父节点（避免无向图的回溯循环），验证两个核心规则：

• 每个非叶子节点必须恰好有两个子节点（邻接节点中排除父节点后，剩余节点数为2）。
• 所有叶子节点的深度必须等于 D - 1（根节点深度为0，叶子在最后一层）。

伪代码实现 #

function isPerfectBinaryTree(adjList):
    n = len(adjList)
    
    // 步骤1：节点数校验
    if n == 0:
        return false
    if n == 1:
        return true  // 单节点是深度1的完美二叉树
    
    D = log2(n + 1)
    if not is_integer(D) or D < 2:
        return false
    
    // 步骤2：度数校验与根节点查找
    root = -1
    for node in range(n):
        degree = len(adjList[node])
        if degree == 2:
            if root != -1:
                return false  // 多个根节点，不符合
            root = node
        elif degree != 1 and degree != 3:
            return false  // 度数非法
    
    if root == -1:
        return false  // 找不到符合要求的根节点
    
    // 步骤3：DFS验证结构
    leaf_target_depth = D - 1
    valid = true
    first_leaf_depth = -1
    
    def dfs(current_node, parent_node, current_depth):
        nonlocal valid, first_leaf_depth
        if not valid:
            return  // 提前终止，优化效率
        
        // 获取当前节点的子节点（排除父节点）
        children = [neighbor for neighbor in adjList[current_node] if neighbor != parent_node]
        
        if len(children) == 0:
            // 叶子节点：检查深度是否一致
            if first_leaf_depth == -1:
                first_leaf_depth = current_depth
            else:
                if current_depth != first_leaf_depth:
                    valid = false
            return
        elif len(children) != 2:
            // 非叶子节点必须恰好有两个子节点
            valid = false
            return
        
        // 递归遍历两个子节点
        for child in children:
            dfs(child, current_node, current_depth + 1)
    
    dfs(root, -1, 0)
    
    // 最后验证叶子深度是否等于目标深度
    return valid and (first_leaf_depth == leaf_target_depth)

关键细节说明 #

• 父节点跟踪：无向图的邻接表包含双向连接，DFS时必须排除父节点，否则会陷入循环。
• 提前终止：一旦发现任何不符合规则的情况（比如子节点数不对、叶子深度不一致），立即终止遍历，提升效率。
• 边界覆盖：单独处理单节点的情况，避免度数校验逻辑误判。

内容的提问来源于stack exchange，提问作者Ellis Thompson