leetcode-二叉树的层序遍历-113

题目要求
  给定一个二叉树，确定他是否是一个完全二叉树。完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。
解析
  广度优先搜索，入队出队
代码实现

class Solution {
public:bool isCompleteTree(TreeNode* root) {//如果是空树，满足完全二叉树要求if(root == nullptr)return true;//增加队列进行记录节点queue<TreeNode*> q;//加入跟节点q.push(root);//增加标志位，用于记录叶子第一次出现空的位置bool flag = false;//如果队列中没东西了，说明整个树遍历完了while(!q.empty()){//用于记录队列中的元素个数int sz = q.size();for(int i = 0; i < sz; i++){//用于记录队列中当前处理的节点TreeNode* cur = q.front();//将处理的元素移出队列q.pop();//首次遇到空的节点，将标志为设置为trueif(cur == nullptr)flag = true;else{//如果已经有空节点，那不应该后面在有节点，否则不满足完全二叉树要求，返回falseif(flag)return false;else {//将当前节点的左节点和右节点加入队列q.push(cur->left);q.push(cur->right);}}}}return true;}
};