编写函数，判断一棵二叉树是否是完全二叉树

可利用递归方式编写一个函数，判断一棵二叉树是否是完全二叉树。

判断逻辑如下：

1. 如果二叉树为空，则是完全二叉树。

2. 如果二叉树不为空，但左子树为空，右子树不为空，则不是完全二叉树。

3. 如果二叉树不为空，但左子树不为空，右子树为空或者左右子树的高度差大于1，则不是完全二叉树。

4. 如果二叉树不为空，且左右子树的高度相同或者差为1，并且左子树是一棵完全二叉树，右子树是一棵满二叉树，则是完全二叉树；或者左子树为一棵满二叉树，右子树是一棵完全二叉树，则也是一棵完全二叉树。

相关问题

编写函数，判断一颗二叉树是否是完全二叉树

可以使用递归的方式判断一棵二叉树是否是完全二叉树。对于一个节点，如果它的左子树为空但右子树不为空，或者它的左右子树个数不相等，那么它就不是完全二叉树。如果该节点是叶子节点，那么之后遍历的所有节点都必须是叶子节点，否则它就不是完全二叉树。遍历过程可以使用层次遍历或先序遍历等方式实现。

. 编写函数实现判断二叉树是否为完全二叉树。（空二叉树是完全 二叉树）

判断一个给定的二叉树是否为完全二叉树，可以通过遍历节点并检查每个层级的节点数是否满足完全二叉树的要求来实现。在完全二叉树中，除了最后一层外，每一层的节点都是满的，且最右边的节点都尽可能靠左。

以下是一个简单的C语言函数，用于判断一个二叉树是否为完全二叉树：

#include <stdbool.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 判断是否为完全二叉树辅助函数
bool isCompleteBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return true; // 空树视为完全二叉树
    }
    
    queue<TreeNode*> q; // 使用队列存储节点
    q.push(root);

    while (!q.empty()) {
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();

            if (node->left != NULL && node->right != NULL) { // 如果当前节点有两个子节点
                q.push(node->left);
                q.push(node->right);
            } else {
                // 检查是否有节点未填满当前层级的剩余位置
                bool hasIncompleteLevel = false;
                if (levelSize > 1 && node->left != NULL) {
                    hasIncompleteLevel = true;
                } else if (levelSize > 0 && node->right != NULL) {
                    hasIncompleteLevel = true;
                }

                if (hasIncompleteLevel) {
                    return false; // 找到不完整层级，直接返回false
                }
            }
        }
    }

    return true; // 遍历完所有节点都没找到不完整层级，说明是完全二叉树
}

这个函数首先创建一个队列并将根节点放入。然后在每一轮循环中，处理当前层级的所有节点，如果遇到节点有右孩子但没有左孩子（或相反），则说明当前层级不满，立即返回`false`。只有当所有层级都被正确填充时，才返回`true`表示完全二叉树。