958. Check Completeness of a Binary Tree
给一棵 binary tree，
问这是否是一棵 complete binary tree，
也就是除了最下面一层以外，深度 h 的节点数量都有 2^h 个节点 (root 的深度为 0)，
并且最下面一层的节点都是往左侧靠。
Example 1:
Input: root = [1,2,3,4,5,6]
Output: true
Explanation:
https://assets.leetcode.com/uploads/2018/12/15/complete-binary-tree-1.png
深度 0 有 1 个 node，深度 1 有 2 个 node，最下层 3 个都是往左侧靠，符合定义。
Example 2:
Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation:
https://assets.leetcode.com/uploads/2018/12/15/complete-binary-tree-2.png
最下层的 5 跟 7 之间有空隙，所以不是 complete binary tree。
解题思路:
重新帮 node 进行编号，root 为 1，
对于任意一个 node i，left child 编号为 i*2，right child 编号为 i*2+1。
对于一个 n 个 node 的 complete binary tree，node 的编号会落在 [1,n]，
在 DFS 遍历所有 node 时纪录总共有多少个 node 以及编号最大值，
编号最大值与 node 数量相等时即说明这是一个 complete binary tree。
因为此题限制 node 数量最多为 100，为了避免编号时 overflow，
若是发现编号大于 100 则可以剪枝并确定这不是棵 complete binary tree。
C++ code:
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
int max_id = 0, node_num = 0;
dfs(root, 1, max_id, node_num);
return max_id == node_num;
}
void dfs(TreeNode *p, int id, int &max_id, int &node_num){
if(!p) return;
max_id = max(max_id, id);
node_num++;
if(max_id > 100) return;
dfs(p->left, id*2, max_id, node_num);
dfs(p->right, id*2+1, max_id, node_num);
}
};