Leetcode 901-1000

958. Check Completeness of a Binary Tree (Medium)

判断一棵树是不是完全二叉树 Complete Binary Tree

完全二叉树指最多只有最后一层不满，且不满的一层所有元素必须靠左排列

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

思路

层次遍历二叉树，发现一个点没有孩子后（按顺序，如果没有左孩子，这个节点也不能有右节点），之后的节点都不能有孩子

bool isCompleteTree(TreeNode* root) {
    if (root == nullptr) return true;
    queue<TreeNode*> q;
    q.push(root);
    bool hasChild = true;
    while(!q.empty()) {
        int size = q.size();
        while (size --) {
            TreeNode* node = q.front();
            q.pop();
            if (node->left == nullptr && node->right != nullptr) return false;
            if (!hasChild && node->left != nullptr) return false;
            if (node->left == nullptr || node->right == nullptr) hasChild = false;
            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }
    }
    return true;
}