[LeetCode]Check Completeness of a Binary Tree

题目链接

这道题需要我们check给定的binary tree是不是complete binary tree，我们需要verify以下几点：

1. 是不是只有最后一层是不满的，换言之，除了最后一层外，其他的层数h(从零开始)的节点数量应该为2^h
2. 如果最后一层是不满的话，是不是所有节点都尽量向左靠拢

为了verify这两点，我们需要使用层序遍历，在check每一层的时候验证以上两点。假设Tree的size为N，时间复杂度O(N)，空间复杂度O(N)，代码如下：

此外，我们可以给所有的节点标号。根节点为0，从上到下，从左到右递增，其他节点按照应该出现的位置标记一个整数。如果给定的树是complete binary tree，那么所有的节点的编号应当是从0到N-1连续的数，我们只需要check最后一个数是不是等于N - 1即可。时间复杂度O(N)，空间复杂度O(N)，代码如下：