当前位置：首页 > article >正文

每日一题-判断是不是完全二叉树

article 2025/3/1 11:57:10

判断是否是完全二叉树

- 题目
- 示例
- - 示例 1
  - 示例 2
  - 示例 3
- 题解
- - 思路
  - 算法步骤
  - 代码实现
  - 代码解释
  - 复杂度分析
- 总结

题目

描述
给定一个二叉树，判断它是否是一个完全二叉树。

完全二叉树的定义：
若二叉树的深度为 $h$ ，除了第 $h$ 层外，其它各层的节点数都达到最大个数，第 $h$ 层所有的叶子节点都连续集中在最左边，这就是完全二叉树。第 $h$ 层可能包含 $1~2^h]$ 个节点。

数据范围

节点数： $\leq n \leq 100$

示例

在这里插入图片描述

示例 1

输入：

{1, 2, 3, 4, 5, 6}

输出：

true

示例 2

在这里插入图片描述

输入：

{1, 2, 3, 4, 5, 6, 7}

输出：

true

示例 3

在这里插入图片描述

输入：

{1, 2, 3, 4, 5, #, 6}

输出：

false

题解

思路

完全二叉树的判断方法可以通过层序遍历（广度优先遍历）来实现：

层序遍历过程中，如果遇到某个节点的左右子节点为空，但后续节点仍然存在，则说明该二叉树不是完全二叉树。
也就是说，在遇到一个空节点后，后面所有节点必须也是空节点，否则就违反了完全二叉树的定义。

算法步骤

使用队列进行层序遍历，遍历每一个节点。
如果节点为空，标记为已遇到空节点。
如果节点非空，但已经遇到过空节点，则返回 false，因为在空节点之后应该没有非空节点。
如果层序遍历完毕，且没有违反完全二叉树的条件，则返回 true。

代码实现

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

/**
 * 结构体定义
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

/**
 * 队列结构体
 */
typedef struct {
    struct TreeNode** data;
    int front;
    int rear;
    int capacity;
} queue;

/**
 * 创建队列
 */
queue* createQueue(int capacity) {
    queue* q = (queue*)malloc(sizeof(queue));
    q->data = (struct TreeNode**)malloc(capacity * sizeof(struct TreeNode*));
    q->front = 0;
    q->rear = 0;
    q->capacity = capacity;
    return q;
}

/**
 * 判断队列是否为空
 */
bool isEmpty(queue* q) {
    return q->front == q->rear;
}

/**
 * 从队列中弹出元素
 */
struct TreeNode* pop(queue* q) {
    return q->data[q->front++];
}

/**
 * 将节点插入队列
 */
void push(queue* q, struct TreeNode* node) {
    if (q->rear < q->capacity) {
        q->data[q->rear++] = node;
    }
}

/**
 * 释放队列内存
 */
void freeQueue(queue* q) {
    free(q->data);
    free(q);
}

/**
 * 判断二叉树是否是完全二叉树
 */
bool isCompleteTree(struct TreeNode* root) {
    if (root == NULL) {
        return true; // 空树是完全二叉树
    }

    queue* q = createQueue(1000); // 创建队列用于层序遍历
    bool flag = false; // 标记是否已遇到空节点
    push(q, root); // 将根节点入队

    while (!isEmpty(q)) {
        struct TreeNode* current = pop(q); // 弹出队列中的节点
        
        if (current == NULL) {
            flag = true; // 遇到空节点，标记为true
        } else {
            if (flag) {
                return false; // 如果之前遇到过空节点，现在还遇到非空节点，则返回false
            }
            push(q, current->left);  // 左子节点入队
            push(q, current->right); // 右子节点入队
        }
    }

    freeQueue(q); // 释放队列
    return true; // 完全二叉树
}

代码解释

队列操作：
- 定义了一个队列 queue，用于层序遍历二叉树。
- 使用 push 函数将节点入队，pop 函数从队列中弹出节点。
- 使用 isEmpty 函数判断队列是否为空。
isCompleteTree 函数：
- 使用队列进行层序遍历。
- 如果当前节点为 NULL，则说明该节点为空节点，标记 flag 为 true。
- 如果在遇到空节点后还遇到非空节点，说明该二叉树不满足完全二叉树的定义，返回 false。
- 如果遍历完成后没有违反完全二叉树的规则，返回 true。