BM35. 判断是不是完全二叉树
描述
示例1
输入:
{1,2,3,4,5,6}
输出:
true
示例2
输入:
{1,2,3,4,5,6,7}
输出:
true
示例3
输入:
{1,2,3,4,5,#,6}
输出:
false
C++ 解法, 执行用时: 2ms, 内存消耗: 396KB, 提交时间: 2022-02-09
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isCompleteTree(TreeNode* root)
{
queue<TreeNode*> que;
que.push(root);
TreeNode *pre = root;
while(que.empty()==false)
{
int len = que.size();
TreeNode *top = que.front();
if(pre==NULL && top!=NULL)
return false;
if(top!=NULL && top->left==NULL && top->right != NULL)
return false;
if(top)
{
que.push(top->left);
que.push(top->right);
}
que.pop();
pre = top;
}
return true;
}
};
class Solution1 {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isCompleteTree(TreeNode* root)
{
queue<TreeNode*> que;
que.push(root);
TreeNode *pre = root;
while(que.empty()==false)
{
int len = que.size();
while(len--)
{
TreeNode *top = que.front();
if(pre==NULL && top!=NULL)
return false;
if(top!=NULL && top->left==NULL && top->right != NULL)
return false;
if(top)
{
que.push(top->left);
que.push(top->right);
}
que.pop();
pre = top;
}
}
return true;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2022-02-10
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isCompleteTree(TreeNode* root) {
// write code here
if(root == NULL){
return false;
}
queue<TreeNode*> result;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* tmp = q.front();
result.push(tmp);
if(tmp == NULL){
q.pop();
continue;
}
q.push(tmp->left);
q.push(tmp->right);
q.pop();
}
bool flag = false;
while(!result.empty()){
TreeNode* tmp = result.front();
if(flag&&tmp!=NULL){
return false;
}
if(tmp == NULL){
flag = true;
}
result.pop();
}
return true;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 424KB, 提交时间: 2021-12-05
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isCompleteTree(TreeNode* root) {
// write code here
if(!root) return true;
int depth = maxDepth(root), currentDepth = 1;
queue<TreeNode*> que;
que.push(root);
while(!que.empty() && currentDepth < depth){
int size = que.size();
if(currentDepth != depth - 1){
//if(size != pow(2, currentDepth - 1)) return false;
for(int i = 0; i < size; i++){
TreeNode* newNode = que.front();
que.pop();
if(newNode -> left) que.push(newNode -> left);
else return false;
if(newNode -> right) que.push(newNode -> right);
else return false;
}
}
else{
bool flag = false;
for(int i = 0; i < size; i++){
TreeNode* newNode = que.front();
que.pop();
if(newNode -> left){
if(flag) return false;
que.push(newNode -> left);
}
else
if(!flag) flag = true;
if(newNode -> right){
if(flag) return false;
que.push(newNode -> right);
}
else
if(!flag) flag = true;
}
}
++currentDepth;
}
return true;
}
int maxDepth(TreeNode* root){
if(!root) return 0;
int leftDepth = maxDepth(root -> left);
int rightDepth = maxDepth(root -> right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
};
C++ 解法, 执行用时: 2ms, 内存消耗: 484KB, 提交时间: 2022-03-13
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isCompleteTree(TreeNode* root) {
// write code here
if(root == nullptr){
return true;
}
queue<TreeNode*> Q;
Q.push(root);
int flag = 0;
while(!Q.empty()){
int cur_size = Q.size();
for(int i=0; i<cur_size; i++){
auto node = Q.front();
Q.pop();
if(flag == 1 && node != nullptr){
return false;
}
if(node == nullptr){
flag = 1;
}
else{
Q.push(node->left);
Q.push(node->right);
}
}
}
return true;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-05-08
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
if (root == NULL)return true;
queue<TreeNode*>que;
que.push(root);
int flag = false;
while(!que.empty()) {
int size = que.size();
for (int i = 0; i < size;i++) {
TreeNode* node = que.front();
que.pop();
if (node == NULL)flag = true;
else {
if (flag == true)return false;
que.push(node->left);
que.push(node->right);
}
}
}
return true;
}
};