C++实现二叉树的完全性校验 _ 队列层序遍历逻辑【源码】-C++-PHP中文网

完全二叉树是除最后一层外每层节点全满、且最后一层节点从左到右连续排列的二叉树；校验关键点是层序遍历中首次遇到空节点后，后续所有节点必须为空，不可出现非空节点。

c++实现二叉树的完全性校验 _ 队列层序遍历逻辑【源码】

什么是完全二叉树？校验的关键判断点在哪

完全二叉树不是“左右平衡”，而是“从上到下、从左到右连续填充”的结构：一旦某节点缺少左子或右子，其后的所有节点都必须是叶子，且不能有空缺。校验本质是检查层序遍历中是否出现「非空节点之后又遇到空节点」的情况。

用队列做层序遍历最直接：把根入队，每次出队一个节点，将其左右子（无论是否为空）依次入队；一旦遇到第一个 nullptr，后续所有出队元素都必须是 nullptr，否则就不是完全二叉树。

用 `std::queue` 层序遍历时的三个关键细节

很多人写错是因为没处理好空指针入队、提前终止、以及边界情况。注意以下几点：

必须将 nullptr 也入队（否则无法检测“空洞后还有非空”）
遇到第一个 nullptr 后，要继续出队并检查剩余所有元素——不能一见到 nullptr 就 return true
空树（root == nullptr）是完全二叉树，需单独判空

示例逻辑片段：

bool isCompleteTree(TreeNode* root) {
    if (!root) return true;
    queue<treenode> q;
    q.push(root);
    bool seenNull = false;
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        if (!node) {
            seenNull = true;
        } else {
            if (seenNull) return false; // 非空节点出现在空节点之后
            q.push(node->left);
            q.push(node->right);
        }
    }
    return true;
}</treenode>

`TreeNode` 定义和测试时容易漏掉的兼容性问题

如果你复用 LeetCode 的 TreeNode 结构，注意它默认构造函数不初始化 left/right，野指针会导致未定义行为。务必显式初始化：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

另外，某些本地编译环境（如旧版 GCC）对 nullptr 支持弱，若报错可临时替换为 NULL，但更推荐启用 C++11 及以上标准（-std=c++11）。