用c++编写程序，判断一颗给定的二叉树是不是完全二叉树

在C++中，判断一棵给定的二叉树是否是完全二叉树，可以采用递归的方式。完全二叉树的特点是从上到下每一层都是满的，除了最后一层，如果存在，所有的节点都尽可能地靠左。

以下是一个简单的算法步骤：

1. 定义一个辅助函数，用于递归遍历二叉树，同时检查当前节点是否有右孩子，并记录右孩子的高度。
2. 如果当前节点为空，说明已经到达叶子节点，返回true，因为这是完全二叉树的一个必要条件。
3. 检查当前节点是否有右孩子，如果没有，则继续检查其左子树是否满足完全二叉树的要求，即左子树也是完全二叉树。
4. 如果有右孩子，那么需要比较当前节点的高度与其右孩子的高度加一是否相等。如果不相等，说明不是完全二叉树，返回false。
5. 如果右孩子存在并且高度相同，继续对右子树进行相同的判断。

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

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true; // 空树视为完全二叉树

    bool has_right = (root->right != nullptr);
    int left_height = height(root->left);

    // 只有一个节点的情况也视为完全二叉树
    if (!has_right || left_height == 0) return true;

    // 非空且非叶子节点，检查右子树的高度是否等于左子树的高度加1
    return height(root->right) == left_height + 1;
}

int height(TreeNode* node) {
    if (node == nullptr) return 0;
    return 1 + std::max(height(node->left), height(node->right));
}