题解 | 判断是不是完全二叉树

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
  //采用广度优先搜索，并且是从每一层的右边进行检测，遇到有节点且再次遇到空节点说明有空缺即false；
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;

        q.push(root);
        int storey = 1;

        while(!q.empty()){ //层循环
            int flag = 0;  //0表示右边还没有节点,1表示右边已经有了节点，遇到空节点就检测flag状态
            for(int i=1; i<=storey && !q.empty(); i++){ //层内处理，注意队列不能为空，
                TreeNode* node = q.front();q.pop();
                if(node->right){
                    q.push(node->right);
                    flag = 1;
                }else if(!node->right && flag == 1){ //空节点但是右边已经有节点了；
                    return false;
                } //空节点但空节点右边都是空节点，合法，不处理；

                if(node->left){
                    q.push(node->left);
                    flag = 1;
                }else if(!node->left && flag ==1){
                    return false;
                }
            }
            storey = storey*2;
        }

        return true;
    }
};