GESP 六级 · GESP 202503 C++ 六级 第 4 题

以下关于完全二叉树的代码描述，正确的是（ ）。

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasNull = false;
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        if (node == nullptr) {
            hasNull = true;
        } else {
            if (hasNull) return false;
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}

逻辑代数运算：与(∧/×)、或(∨/+)、非(┐/¬)。德摩根律：┐(A∧B)=┐A∨┐B，┐(A∨B)=┐A∧┐B。

注意德摩根律的正确应用：┐(A∧B)=┐A∨┐B，┐(A∨B)=┐A∧┐B。C++中逻辑运算符有短路求值特性。

【考点】二叉树层序遍历｜完全二叉树性质｜布尔状态控制

🎯 考纲定位 六级《树与二叉树》模块下“遍历”考点，命题人借完全二叉树特性卡住学生——多数只背“满二叉树”定义，却混淆“完全二叉树”的层序遍历特征。

🧠 解题思维 代码用队列做BFS遍历，hasNull标记是否遇到空节点。遇到空节点前若有非空节点，立即返回false——这就是“完全二叉树”的核心判定逻辑：左子树先于右子树，且最后一层从左到右填满。

🪤 陷阱拆解 A项混淆“满二叉树”与“完全二叉树”，满二叉要求每层节点数=2^k，而代码只保证非空节点顺序；C项BST需比较值大小，代码无比较逻辑；D项高度计算需统计层数，此函数仅返回布尔值。最阴险处在于“遇到空节点前若有非空节点就返回false”，命题人用hasNull标记层序遍历中的“断档”，若后面还有节点，说明最后一层没填满，直接判假。

🔄 反命题思维 若把if (hasNull) return false;改成if (hasNull) return true;，则代码判断“是否存在空节点”，完全二叉树未必有，此改动会误判所有满二叉树。刷到层序遍历题，先问“空节点标志用在何处”——若在非空节点判断中，必考完全二叉树；若在统计节点数中，可能考满二叉树。