判断一棵树是否是完全二叉树

这道题可以看作是层序遍历的变形。

在二叉树的层序遍历中，我们借助一个数据结构队列，根据其先进先出的性质，实现层序遍历。

可以定义一个flag标志位，一旦遇到空节点，标志位生效。

相关代码如下：

#include<iostream>
#include<queue>
using namespace std;

struct Node
{
    int _data;
    Node* _left;
    Node* _right;
    Node(const int& x)
        : _data(x)
        , _left(NULL)
        , _right(NULL)
    {}
};

//层序遍历
void LevelOrder(Node* root)
{
    if (root == NULL)
        return;
    queue<Node*> q;

    Node* cur = root;
    q.push(cur);
    while (!q.empty())
    {
        Node* front = q.front();
        cout << front->_data << " ";
        q.pop();
        if (front->_left)
            q.push(front->_left);
        if (front->_right)
            q.push(front->_right);
    }
    cout << endl;
}

bool IsCompleteTree(Node* root)
{
    if (root == NULL)
        return false;
    queue<Node*> q;
    bool flag = 0;
    Node* cur = root;
    q.push(cur);
    while (!q.empty())
    {
        Node* front = q.front();
        q.pop();
        if (front->_left)
        {
            if (flag)
                return false;
            q.push(front->_left);
        }
        else
        {
            if (flag == 0)
                flag = 1;
        }
        if (front->_right)
        {
            if (flag)
                return false;
            q.push(front->_right);
        }
        else
        {
            if (flag == 0)
                flag = 1;
        }
    }
    return true;
}

int main()
{
    Node* p1 = new Node(1);
    Node* p2 = new Node(2);
    Node* p3 = new Node(3);
    Node* p4 = new Node(4);
    Node* p5 = new Node(5);
    Node* p6 = new Node(6);

    //完全二叉树
    /*p1->_left = p2;
    p1->_right = p3;
    p2->_left = p4;
    p2->_right = p5;
    p3->_left = p6;*/

    //非完全二叉树
    p1->_left = p2;
    p1->_right = p3;
    p2->_left = p4;
    p2->_right = p5;
    p3->_right = p6;

    LevelOrder(p1);
    cout << IsCompleteTree(p1) << endl;
    return 0;
}