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

方法：BFS，辅助队列

本质是广度优先搜索，利用辅助队列进行层序遍历。

如果一个二叉树是完全二叉树，那么层序遍历时，第一个空结点也是它的最后一个空结点；否则就不是完全二叉树。

时间复杂度：o(n)。最坏情况需要遍历二叉树的所有结点。

空间复杂度：o(n)。需要辅助队列进行二叉树的层序遍历

class Solution {
  public:
    queue<TreeNode*> res;
    bool isCompleteTree(TreeNode* root) {
        if (root == nullptr)
            return true;
        res.push(root);
        //层间遍历第一个结点为空的标志
        bool flag = false;
        while (!res.empty()) {
            int length = res.size();
            for (int i = 0; i < length; i++) {
                TreeNode* cur = res.front();
                if (cur == nullptr) {
                    flag = true;
                } else {
                    //如果第一个空节点后还有不为空的节点，则不是完全二叉树
                    if (flag == true)
                        return false;
                    res.push(res.front()->left);
                    res.push(res.front()->right);
                }
                res.pop();
            }
        }
        return true;
    }
};