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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
bool isCompleteTree(struct TreeNode* root ) {
    // write code here
    if(root == NULL)
    return false;
    //如果是空树，返回false
    struct TreeNode* Queue[100];
    //初始化一个数组作为队列，用于层序遍历
    int head = 0;
    int tail = 0;
    Queue[tail++] = root;
    while(head!=tail)
    {
        struct TreeNode* node = Queue[head];
        //创建新节点

        if(node->left == NULL && node->right != NULL)
        return false;
        //如果左叶子为空右叶子不为空直接返回false

        if(node->left != NULL && node->right != NULL)
        {
            Queue[tail++] = node->left;
            Queue[tail++] = node->right;
            head++;
        }
        //如果左右叶子都不为空，判断下一个节点

        if((node->left != NULL && node->right == NULL)||(node->left == NULL && node->right == NULL))
        //如果都是叶子节点或者没有右节点
        {
            if(node->left != NULL && node->right == NULL)//没有右节点，入队左节点，判断下一个节点
                    Queue[tail++] = node->left;

            head+=1;
            while(head != tail)
            {
                struct TreeNode* node = Queue[head];
            
                if(node->left == NULL && node->right == NULL)
                head++;//判断是不是叶子结点，如果是叶子节点，那么出队头节点，检查下一个节点
                else
                return false;
            }
            return true;
        }
    }
    return true;
}