检查二叉树是否complete。完全二叉树只有最后一层不完整,且最后一层只有右侧可能有连着的空缺。检查层信息,用BFS。完整二叉树seriliaze后中间不会出现null,利用这条性质在BFS时无论l和r是否为null都往q里插,当弹出遇到null后如果是complete的,BFS应该结束;否则不是complete的。
/*
* @lc app=leetcode id=958 lang=cpp
*
* [958] Check Completeness of a Binary Tree
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
if (root == nullptr) return false;
queue<TreeNode*> q;
q.push(root);
bool end = false;
while (!q.empty()) {
const auto t = q.front();
q.pop();
if (t == nullptr) end = true;
else {
if (end) return false;
q.push(t->left);
q.push(t->right);
}
}
return true;
}
};
// @lc code=end