判断二叉树是否为完全二叉树

判断方法

• 使用层遍历
• 如果一个节点只有右孩子没有左孩子，那么不是完全二叉树
• 如果一个节点只有左孩子没有右孩子，或者没有孩子，后面的节点必须全是叶节点

代码

#include <iostream>
#include <queue>

//节点
struct Node {
    int value;
    Node* parent;
    Node* left;
    Node* right;

    Node(int v = 0): value(v), parent(nullptr), left(nullptr), right(nullptr) {}
};

//销毁二叉树
void destroy_tree(Node* root) {
    if (root == nullptr) {
        return;
    }

    destroy_tree(root->left);
    destroy_tree(root->right);

    delete root;
}

//是否为完全二叉树
bool is_CBTree(Node* &head) {
    if (head == nullptr) {
        return true;
    }
    Node *left;
    Node *right;
    bool leaf = false;
    std::queue<Node*> q;
    q.push(head);
    Node* root;
    while (!q.empty()) {
        root = q.front();
        q.pop();
        left = root->left;
        right = root->right;
        //如果一个节点只有左孩子没有右孩子，或者没有孩子，后面的节点必须全是叶节点
        if (leaf && (right != nullptr || left != nullptr)) {
            return false;
        }
        //如果一个节点只有右孩子没有左孩子，那么不是完全二叉树
        if (right != nullptr && left == nullptr) {
            return false;
        }

        if (left != nullptr) {
            q.push(left);
        }
        if (right != nullptr) {
            q.push(right);
        }
        //如果一个节点没有右孩子，后面的节点必须全是叶节点
        if (right == nullptr) {
            leaf = true;
        }
    }

    return true;
}

int main(void)
{
    Node* head1 = new Node(0);
    Node* node11 = new Node(1);
    Node* node12 = new Node(2);
    head1->left = node11;
    head1->right = node12;

    std::cout << "head1 is CBTree -----> " << std::boolalpha << is_CBTree(head1) << std::endl;

    //创建一颗不平衡树
    Node* head2 = new Node(0);
    Node* node21 = new Node(1);
    Node* node22 = new Node(2);
    head2->left = node21;
    node21->right = node22;
    std::cout << "head2 is CBTree -----> " << std::boolalpha << is_CBTree(head2) << std::endl;

    destroy_tree(head1);
    destroy_tree(head2);
    return 0;
}