完全二叉树的判断代码

以下是判断完全二叉树的代码实现：

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

该算法使用了层序遍历的思想，将每一层的节点按顺序加入队列中，如果在遍历过程中出现了空节点，那么后面的节点必须全部为空节点才能保证是完全二叉树，否则就不是完全二叉树。

相关问题

判断完全二叉树王道代码

### 判断完全二叉树的代码实现

为了判断一棵二叉树是否为完全二叉树，可以采用层序遍历的方法。一旦遇到第一个空节点之后不应该再有非空节点出现，否则就不是完全二叉树。

以下是基于此逻辑使用C语言编写的函数来检测给定的二叉树是否为完全二叉树[^5]：

#include <stdbool.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

bool isCompleteBinaryTree(TreeNode* root) {
    if (!root) return true; // 空树视为完全二叉树
    
    // 创建一个队列用于层序遍历
    typedef struct QueueNode {
        TreeNode* node;
        struct QueueNode* next;
    } QueueNode;
    
    QueueNode* queue = NULL, *rear = NULL, *tempQueueNode;
    bool metNull = false;
    
    // 初始化队列并加入根节点
    tempQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    tempQueueNode->node = root;
    tempQueueNode->next = NULL;
    queue = rear = tempQueueNode;
    
    while (queue != NULL) {
        // 出队操作
        tempQueueNode = queue;
        TreeNode* currentNode = tempQueueNode->node;
        queue = queue->next;
        
        free(tempQueueNode);
        
        if (currentNode == NULL) {
            metNull = true;
        } else { // 当前节点不为空
            if (metNull) return false; // 如果之前已经遇到了null，则返回false
            
            // 将左右孩子依次入队
            tempQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
            tempQueueNode->node = currentNode->left;
            tempQueueNode->next = NULL;
            
            if (rear == NULL) {
                queue = rear = tempQueueNode;
            } else {
                rear->next = tempQueueNode;
                rear = tempQueueNode;
            }
            
            tempQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
            tempQueueNode->node = currentNode->right;
            tempQueueNode->next = NULL;
            
            rear->next = tempQueueNode;
            rear = tempQueueNode;
        }
    }

    return true;
}

上述程序定义了一个`isCompleteBinaryTree`函数接收指向二叉树根节点的指针作为参数，并返回布尔类型的值指示该二叉树是否为完全二叉树。这里采用了链表形式的手动管理队列来进行广度优先搜索(BFS)，即所谓的层序遍历。

完全二叉树判断的伪代码

完全二叉树判断的伪代码如下：

1. 定义一个队列，用于存储待检查的节点。
2. 将根节点入队。
3. 循环执行以下步骤，直到队列为空：
1. 出队一个节点，并检查其左右子节点是否存在。
- 如果左子节点不存在但右子节点存在，返回 false。
- 如果左子节点存在但右子节点不存在，或者上一层已经出现了左右子节点不全的情况，后续的节点必须都是叶子节点，否则返回 false。
2. 如果左子节点存在，则将其入队。
3. 如果右子节点存在，则将其入队。
4. 如果队列为空，且所有节点都满足上述条件，则返回 true，表示是完全二叉树；否则返回 false。

伪代码实现：

function isCompleteBinaryTree(root):
    queue = new Queue()
    queue.enqueue(root)
    leafNodeFound = false
    
    while queue is not empty:
        node = queue.dequeue()
        
        if node.left is not null:
            if leafNodeFound or node.right is null:
                return false
            queue.enqueue(node.left)
            
        if node.right is not null:
            if leafNodeFound:
                return false
            queue.enqueue(node.right)
        else:
            leafNodeFound = true
    
    return true

注意：上述伪代码假设已经定义了一个队列数据结构，并实现了相应的 enqueue 和 dequeue 操作。