1 解题思路

本题判断是否是完全二叉树，根据完全二叉树的性质，考虑使用按层次遍历检查。可以先枚举所有不是完全二叉树的形态，当程序检查到该形态后可以直接返回false，全部遍历完成后证明所有结点符合要求，返回true。

所有不是完全二叉树的形态：

（1）某一个结点有右孩子，没有左孩子；

（2）某一个结点只有左结点，右侧的兄弟结点或堂兄弟结点不存在；

（3）某一个结点只有左结点或一个结点都没有，右侧兄弟结点或堂兄弟结点有孩子结点。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        if(!root)
            return true;
        vector<TreeNode*> queue; //按层次遍历，队列里存放同一层所有结点。这里除了vector也能用dequeue。
        queue.push_back(root);
        bool mark = false; //哨兵，如果某个结点只有左结点或一个结点也没有，设为true。注意mark不能再while循环中定义，否则会漏掉不是完全二叉树的第二种形态的情况，可以验证自行验证。
        while(!queue.empty()){       
            for(TreeNode* tmp:queue){
                if(mark && (tmp->left||tmp->right)) //不是完全二叉树的第二种形态或第三种形态，直接返回。
                    return false;  
                if(!tmp->left && tmp->right)//不是完全二叉树的第一种形态。
                    return false;
                if(!tmp->left || !tmp->right) //首次遇到不完全结点时，mark设置为true
                    mark=true;
            }
            int count = queue.size();
		   //当前层所有结点遍历结束，依次出队，将下一层结点按顺序进入队列。
            while(count>0){
                TreeNode* front = queue.at(0); 
                queue.erase(queue.begin());
                if(front->left)
                    queue.push_back(front->left);
                if(front->right)
                queue.push_back(front->right);
                count--;
            }     
        }
	  	//队列为空说明所有结点遍历完成，正常退出循环说明都符合完全二叉树要求，返回true。
        return true;
        
    }
};