题目描述
算法1 $O(N)$
置一个标志位,标志是否出现空节点;如果在空节点之后又出现了叶子节点,那么就不是完全二叉树。
C++ 代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include <cmath>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isCompleteTree(TreeNode* root) {
// write code here
queue<TreeNode*> q;
q.push(root);
TreeNode* p;
bool flag = false;
int n;
while (!q.empty()) {
n = q.size();
for (int i = 0; i < n; i++) {
p = q.front();
q.pop();
//标记第一次遇到空节点
if (p == NULL){
flag = true;
}
else{
//后续访问已经遇到空节点了,说明经过了叶子
if (flag) return false;
q.push(p->left);
q.push(p->right);
}
}
}
return true;
}
};