判断完全二叉树 代码

要判断一棵二叉树是否为完全二叉树，我们需要检查以下条件：

1. 完全二叉树的每个层级都是满的，除了最后一个层级可能不满，但所有节点都尽可能地靠左排列。
2. 如果存在最后一层，则最后一层的所有节点都在左边。

这里有一个简单的C++代码实现，使用深度优先搜索（DFS）遍历二叉树并记录节点的数量，同时跟踪当前层级：

#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 判断是否为完全二叉树
bool isCompleteBinaryTree(TreeNode* root) {
    if (root == nullptr) return true; // 空树视为完全二叉树

    int level = 0, count = 1, node = root;
    while (node != nullptr) {
        ++level;
        if (node->left != nullptr && node->right != nullptr) {
            // 如果左右子节点都存在，更新计数器
            count += 2;
        } else {
            // 否则，只增加1
            count++;
        }
        node = node->left ? node->right : node->left ? node->left : nullptr; // 跟踪下一个节点
    }

    // 遍历结束后，检查是否存在不满足完整性的节点
    for (int i = 1; i < level; ++i) {
        if (count % 2 == 1) { // 偶数层级表示满，奇数层级可能存在未填充节点
            if ((count - 1) / 2 < pow(2, i)) { // 不满足完全二叉树条件
                return false;
            }
        } else {
            if (count < pow(2, i + 1)) { // 最后一层，检查所有节点是否都在左侧
                return false;
            }
        }
        count /= 2;
    }
    return true;
}

int main() {
    // 测试用例
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    cout << (isCompleteBinaryTree(root) ? "是" : "否") << endl; // 输出：是

    // ... 更多测试用例...

    return 0;
}

这个代码首先检查根节点，然后递归遍历二叉树。对于每一层，如果左右都有节点，则数量翻倍；否则，数量加一。遍历完成后，根据规则检查每层节点数量是否满足完全二叉树的定义。