C++ 笔试基础题 27 完全二叉树判断练习题 牛客网 7.9
有一棵二叉树,请设计一个算法判断它是否是完全二叉树。
给定二叉树的根结点root，请返回一个bool值代表它是否为完全二叉树。树的结点个数小于等于500。
该三个二叉树，均为完全二叉树，第一个同时也为满二叉树。
图中例子：不是完全二叉树
链接：https://www.nowcoder.com/courses/1/7/9
来源：牛客网
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class CheckCompletion {
public:
bool chk(TreeNode* root) {
if (root == NULL){
return false;
}
//对列
queue q;
q.push(root);//头结点如 队列
int flag = 0;//标志
while (!q.empty()){//队列不为空
TreeNode* psave = q.front();//取队列 首元素 节点
//节点左孩子为空 右孩子不为空 直接返回false
if (psave->left == NULL && psave->right != NULL){
return false;
}
//节点左孩子不为空 右孩子为空
if (psave->left != NULL && psave->right == NULL){
if (flag == 1){//如果标志位 为1 返回false
return false;
}
flag = 1;//标志位置为1
}
//节点左孩子不为空 且 右孩子不为空 且标志位 为1
if (psave->left != NULL && psave->right != NULL && flag == 1){
return false;//返回false
}
//如果左孩子不为空 左孩子节点压入队列
if (psave->left != NULL){
q.push(psave->left);
}
//如果右孩子不为空 右孩子节点压入队列
if (psave->right != NULL){
q.push(psave->right);
}
q.pop();//弹出队列的首元素 节点
}
return true;
}
};