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;
}