222. 完全二叉树的节点个数（JS实现）
1 题目
给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了*底层节点可能没填满外，其余每层节点数都达到*大值，并且*下面一层的节点都集中在该层*左边的若干位置。若*底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
输入:
1
/
2 3
/ \ /
4 5 6
输出: 6
2 思路
这道题我是层序遍历整个树，统计了一遍节点数量，没有用到完全二叉树这个概念，由于是完全二叉树，则除去*后一层的节点数量为2^d – 1，我们只需要计算完全二叉树*后一层有多少节点，可以给*后一层的节点编号0…2^d – 1，然后用二分算法来加快搜索速率：
1.如果树为空，返回 0。
2.计算树的高度 d(不包含*后一层)。
3.如果 d == 0，返回 1。
4.除*后一层以外的所有节点数为 2^d-1。*后一层的节点数通过二分搜索，检查*后一层有多少个节点。使用函数 exists(idx, d, root) 检查第 idx 节点是否存在。
5.使用二分搜索实现 exists(idx, d, root)。
6.返回 2^d – 1 + *后一层的节点数
3代码
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if (!root) return 0;
    const queqe = [root];
    let index = 0;
    while(queqe.length > 0) {
        let p = queqe.shift();
        index++;
        if (p.left) queqe.push(p.left);
        if (p.right) queqe.push(p.right);
    }
    return index;
};
、