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

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <list>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    bool isBranchEmpty(TreeNode*
                       root) {  //判断根节点左右指针是否为空。都为空，返回true;否则返回false.
        if (root->left == nullptr && root->right == nullptr) {
            return true;
        }
        return false;
    }
  	//使用广度优先搜索算法，用一个队列list记录首次出现空节点的那一层所有节点。只有list中节点满足#1.“非空，非空，...，非空，空，空，空”；2.list前面所有非空节点都没有下一层节点。#这两个条件，树才是完全二叉树
    bool isCompleteTree(TreeNode* root) {
        // write code here
        if (root == nullptr) {
            return true;
        }
        list<TreeNode*> li; //记录每一层的节点
        li.push_back(root);
        bool tag = true;    //如果list中任意节点的下一层节点为空则置为false
        while (tag) {   //循环结束后，list记录第一次出现空节点的那一层节点
            int size = li.size();
            while (size--) {
                if (li.front()->left == nullptr || li.front()->right == nullptr) {
                    tag = false;
                }
                li.push_back(li.front()->left);
                li.push_back(li.front()->right);
                li.pop_front();
            }
        }
        TreeNode* p = li.front();   //循环结束后，list记录第一次出现空节点的那一层节点
        li.pop_front();
        while (!li.empty()) {
            if (p != nullptr && isBranchEmpty(p) == false) {    //如果一个节点不为空，节点下一层存在节点，证明不是完全树
                return false;
            }
            if (p == nullptr && li.front() != nullptr) {    //如果上一个节点为空，下一个节点不为空，证明不是完全树
                return false;
            }
            p = li.front();
            li.pop_front();
        }
        return true;
    }
};