【打卡】牛客网：BM35 判断是不是完全二叉树

二叉树"/>

【打卡】牛客网：BM35 判断是不是完全二叉树

自己写的：

第一行到倒数第三行都是满的，最后判断倒数第二行的情况。

但是，第一个while循环，考虑迭代的停止条件时，如果是根据节点个数进行判断，那么计算98层节点个数的时候，n的存储范围不够。所以改成根据层数进行判断。

/*** 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布尔型*/int maxDepth(TreeNode* root) {if (root == NULL)return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}bool isCompleteTree(TreeNode* root) {// write code hereint h = maxDepth(root);if(h == 1)return true;if(h == 2)if(root->left == NULL && root->right != NULL)return false;elsereturn true;int hCur = 1;queue<TreeNode*> q;q.push(root);// 第一层到倒数第三层while(hCur != h) {hCur ++;if (q.front()->left == NULL || q.front()->right == NULL)return false;q.push(q.front()->left);q.push(q.front()->right);q.pop();}// 倒数第二层while (!q.empty()) {if (q.front()->right == NULL) {q.pop();while (!q.empty()) {if (q.front()->left != NULL && q.front()->right != NULL)return false;q.pop();}} else {if (q.front()->left == NULL)return false;elseq.pop();}}return true;}
};

模板的：

①因为完全二叉树，只有最后一行可能出现NULL，所以在层序遍历的时候，不需要考虑子节点是否为空。（以前的做法是，分别判断左右子节点：如果不为空，再push进去。）

②基于①，所以层序遍历不需要考虑“某一个节点的左右子节点为NULL”的相互关系。只需要按照完全二叉树的定义来思考，即完全二叉树的所有元素是紧凑的：靠上的，最后才是靠左的。如果从上往下，再从左往右遍历。那么出现NULL后，再出现一个值，那么最终判断结果一定是false。

/*** 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 hereif(root == NULL)return true;queue<TreeNode*> q;q.push(root);int flag = 0;while(!q.empty()) {for(int i = 0; i < q.size(); i++){TreeNode* cur = q.front();q.pop();if(!cur) // 第二次出错了，if(cur==NULL)是if(!cur)，不是if(cur)！！！flag = 1;else{if(flag)return false;q.push(cur->left);q.push(cur->right);}}}return true;}
};