leetcode 链接：958. 二叉树的完全性检验

题目

给定一个二叉树，确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下：
若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 个节点。）

示例：

输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

输入：[1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点没有尽可能靠向左侧。

解答 & 代码

广度优先遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if(root == nullptr)
            return true;

        queue<TreeNode*> nodeQ;
        nodeQ.push(root);
        bool occurNull = false;        // 代表是否遍历到了一个 nullptr 节点
        // 广度优先遍历
        while(!nodeQ.empty())
        {
            TreeNode* cur = nodeQ.front();
            nodeQ.pop();
            // 如果当前节点为 nullptr，则将 occurNull 置为 true
            if(cur == nullptr)
                occurNull = true;
            else
            {
                // 如果当前节点不为空，且之前已经出现过空节点，则说明不是完全二叉树，直接返回false
                if(occurNull == true)
                    return false;
                // 将左右子节点压入队列
                nodeQ.push(cur->left);
                nodeQ.push(cur->right);
            }
        }
        return true;
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 81.54% 的用户
内存消耗：10.2 MB, 在所有 C++ 提交中击败了 55.55% 的用户