题解 | NO.35#判断是不是完全二叉树#3.12

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
 */
//基本思想：使用循环队列对二叉树进行层次遍历，空结点也入队，当遇到第一个空结点时，判断后续队列中结点是否有
//非空结点，如果有则说明不是完全二叉树；反之则是。
#define SizeMax 100
bool isCompleteTree(struct TreeNode* root ) {
    //空树，直接返回true
    if(root == NULL)
        return true;
    //用队列进行层次遍历，空结点也入队
    struct TreeNode* Queue[SizeMax];
    int head = 0;
    int tail = 0;
    struct TreeNode* temp = NULL;
    //头结点入队
    Queue[tail] = root;
    tail = (tail + 1) % SizeMax;
    //队不空则循环继续
    while(tail > head){
        //对头结点出队
        temp = Queue[head];
        head = (head + 1) % SizeMax;
        //队头结点不为空，则将其孩子结点先左后右依次入队
        if(temp != NULL){
            Queue[tail] = temp->left;
            tail = (tail + 1) % SizeMax;
            Queue[tail] = temp->right;
            tail = (tail + 1) % SizeMax;
        }
        //队头结点为空，跳出循环
        else
            break;
    }
    //遍历队列中剩余结点
    while(tail > head){
        temp = Queue[head];
        head = (head + 1) % SizeMax;
        //若存在非空结点，说明不是完全二叉树
        if(temp != NULL)
            return false;
    }
    //第一个空结点后不存在非空结点，说明是完全二叉树
    return true;
}

//用循环队列就不用担心结点数超过数组了