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

总结一下经验吧，感觉还是要静下心来仔细分析题目，不能急着动笔，不然就会遇到数不尽的坑。练习的时候还可以拿不通过样例调试，实战可没有这种条件。

这一题稍微想想就知道可以用层序遍历。通过检查每一层的结点分布以及这一层的层数与个数的关系来判断到该层为止是否是完全二叉树。

突然想到其实不用一层一层看，直接将层序遍历当成一个整体看，只要出现过一次None结点，而后面又有非None的结点的时候就可以判断不是完全二叉树。如果一层一层看，就需要多一个判断，判断节点数不满的层是不是最后一层，而整体看就不用考虑这个。

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    int offNoneSize(vector<TreeNode*> v) {
        int len = 0;
        for (int i = 0; i < v.size(); i++, len++) {
            if (!v[i]) len--;
        }
        return len;
    }

    bool isCompleteTree(TreeNode* root) {
        if (!root) return false;
        vector<TreeNode*> query;
        query.push_back(root);
        int depth = 0, length;
        TreeNode* tmp;
        while (!query.empty()) {
            length = offNoneSize(query);
            if (length != pow(2, depth)) {
                bool b = false;
                for (int i = 0; i < query.size(); i++) {
                    if (query[i]) {
                        if (b || query[i]->left || query[i]->right) return false;
                    }
                    if (query[i] == NULL) {
                        if (!b) b = true;
                    }
                }
                break;
            }

            for (int i = 0; i < length; i++) {
                query.push_back(query[i]->left);
                query.push_back(query[i]->right);
            }
            query.erase(query.begin(), query.begin() + length);
            depth++;
        }
        return true;
    }
};