题解 | #判断是不是完全二叉树#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */  
//设置一个饱和bool变量，饱和是指一个节点左右孩子都有，只要最少一个孩子不在，就叫不饱和

//完全二叉树的不饱和节点只能是最后一个父节点的和一个孩子处

//如果饱和变量被设置成false之后还遇到不饱和情况，那么这一不是完全二叉树

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    //层序遍历思想
  bool isCompleteTree(TreeNode* root)
{
    if (root == nullptr) //空树直接对
        return true;
    queue<TreeNode*> q; //队列
    q.push(root);
    bool saturate = true; //判断是不是饱和
    while (!q.empty()) //树没有遍历完
    {
        TreeNode* p = q.front(); //层序思想
        q.pop();
        if (p->left) //只要左不是空
        {
            if (!saturate) return false; //在这之前已经不饱和，那么直接错
            q.push(p->left); //如果是饱和的，把不为空的左 入队
        }
        else saturate = false; //左为空，设置为不饱和
        if (p->right)// 同上
        {
            if (!saturate) return false;
            q.push(p->right);
        }
        else saturate = false;
    }
    return true;
}
};