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

//层次遍历判断是不是完全二叉树

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        bool foundNull = false;

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (!node) {
                foundNull = true;
            } else {
                if (foundNull) {
                    return false;
                }
                q.push(node->left);
                q.push(node->right);
            }
        }
        return true;
    }
};

算法思路
我们可以利用层序遍历的特点：
从根节点开始进行层序遍历
如果遇到某个节点为空，那么它之后的所有节点都必须为空
如果遇到空节点后，后面又出现了非空节点，说明不是完全二叉树
算法分析
时间复杂度：O(n)，需要遍历所有节点
空间复杂度：O(n)，最坏情况下队列中需要存储所有节点