Readme

954.Check-Completeness-of-a-Binary-Tree

解法1：

查验是否一棵完全二叉树，有一个固定的技巧。我们将所有的节点按照从高到低，从左往右的顺序依次编号。例如第0层的编号是0，那么第一层的两个节点编号是1,2,那么第二层的四个节点（如果存在的话）编号就是3,4,5,6.其特点是: left index = parent index * 2 +1,right index = parent index * 2 +2.

如果一棵完全二叉树按照上述规则编号的话，理论上等同于严格按照层级顺序来遍历所有节点，那么得到的节点编号是顺序的且是满枝的，并且不会超过总结点数。而其他任何非完全二叉树，按照上述规则编号，则必然会导致有某个节点的编号大于了总节点数目。

解法2：

有一个更直观易懂的方法。一棵完全二叉树最大的特点就是，如果我们做层级遍历，那么在遇到最后一个节点之前，所有的节点都是非空的。

因此我们可以用队列做一个层级的遍历，也就是说，每遇到一个节点就将其左右子节点（即使子节点是空）加入队列中。层级遍历的特点就是从上到下，从左到右，因此当遇到队列中的队首元素是NULL的时候，那么意味着它应该就是整棵树最后的节点，队列中剩下的所有的节点必须都是NULL。这就是完全二叉树的充要条件。

Leetcode Link