Check if a given binary tree is completed. A complete binary tree is one in which every level of the binary tree is completely filled except possibly the last level. Furthermore, all nodes are as far left as possible.

Examples

    5

   /   \

  3     8

/  \

1    4

is completed.

    5

   /   \

  3     8

/  \     \

1    4     11

is not completed.

Corner Cases

• What if the binary tree is null? Return true in this case.

  
  

How is the binary tree represented?

We use the level order traversal sequence with a special symbol "#" denoting the null node.

For Example:

The sequence [1, 2, 3, #, #, 4] represents the following binary tree:

  1

/  \

2   3

   /

  4

思路

使用队列按层次遍历的顺序进行，使用flag记录上一层的状态，默认为false 即对应第一个遍历到根节点的状态。

flag 与 节点状态对应如下：

• 节点为空  flag = true

• 节点非空 flag = false

  
  

运行思路

• root != null 时，使用队列层次遍历，flag = false;

• 节点为空时，flag = true 标记

• 若节点非空

  • 前一个节点为空时，则该二叉树一定不完整。

    • 判断上一个节点是否为空的方式 flag

      
      

  • 前一个节点非空时，则添加节点用于遍历其子节点即可

    
    

• 若节点为空

  • 前一个节点为空时，记录flag = true; 不操作

  • 前一个节点非空时，记录flag = true; 不操作

  • 以上操作可以合并，即当当前节点为空时，前一个节点是否为空都不需要操作，只需要记录当前节点为空即 flag = true;

    
    

• 由于每个节点有两个左右子节点： 每次循环都要对左右两个子节点进行判断

  
  

若该树是完整的，则只有遍历到最后