958. Check Completeness of a Binary Tree
Medium

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Baike:
  In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

测试用例1 ``` Input: [1,2,3,4,5,6] Output: true Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible. ```

Example 2:

测试用例2 ``` Input: [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible. ```

Note:

``` 1.The tree will have between 1 and 100 nodes. ```

  算法思想:看到这个题目,比较容易想到的也许就是层序遍历来判断了。即采用层序遍历的方式遍历结点,如果当前结点是空的,则判断队列里是否还有结点,即该结点之后是否还有结点。如果有,则不是完全二叉树。如果没有,则继续判断直至遍历完所有结点。


Javascript Solution:

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */

var isCompleteTree = function(root) {
    if(root === null) return true   //如果是空树,也是完全二叉树
    let queue = [root]
    while(queue.length != 0){        //层序遍历
        let p = queue.shift()
        if(p){                //区别正常层序遍历判空左右,不判空左右孩子直接进队列
            queue.push(p.left)
            queue.push(p.right)
        }
        else{                //如果当前结点为空,则将队列剩下元素全部弹出,如果非空,则不是完全二叉树。
            while(queue.length != 0){
                let pson = queue.shift()
                if(pson)
                    return false
            }
        }
    }
    return true        //如果为空,跳出循环并返回是完全二叉树
};

C Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isCompleteTree(struct TreeNode* root){
    if(root == NULL) return true;    //如果为空树,则返回是完全二叉树
    int front = -1, rear = -1;
    struct TreeNode *queue[1000];        //c语言没有变长数组,恰巧题目有给出结点在1-100,定1000比较过分的,最好比最大限制多10即可。
    queue[++rear] = root;        //根结点入队
    while( front < rear ){
        struct TreeNode *p = queue[++front];        //队首出队
        if(p!=NULL){                //下面过程同javascript解法
            queue[++rear] = p->left;
            queue[++rear] = p->right;
        }
        else{
            while( front < rear ){
                struct TreeNode *q = queue[++front];
                if(q!=NULL)
                    return false;
            }
        }
    }
    return true;
}