222. 完全二叉树的节点个数

给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

输入: 
    1
   / \
  2   3
 / \  /
4  5 6

输出: 6

解题思路以及知识点：

1. 暴力简单方法之DFS和BFS遍历所有结点，计算节点数。
2. 利用完全二叉树特殊特点，减少对所以有节点的遍历。

方法一：BFS或DFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
let count=0;
var countNodes = function(root) {
    count=0;
    dfs(root)
    return count;
};
function dfs(root){
    if(root===null){
        return
    }
    count++
    dfs(root.left)
    dfs(root.right)
}

方法二：位操作判断左右，二分查找寻找最末端节点。

1. 将完全二叉树的左孩子标记0，右孩子标记1 如下[1,2,3,4,5,6]节点。则可将路径的二进制码当成当前节点的编号，即节点1为（1），节点2为（10），节点3为（11），节点4为（100），节点5为（101），节点6为（110）以此类推，节点n的路径可根据n的二进制编码取得。
2. 完全二叉树特性，可根据深度level确定所有叶子节点n的取值范围即：(1<<level)<=n<=(1<<level+1).eg:当level=2时，叶子节点的编号值大于等于4，小于等于7.
3. 通过二分查找，寻找叶子节点的编号之为k。对k的二进制位进行与操作，根据位的0或1确定路径向右还是向左。eg：6（110）若判断判断二进制第二位的值，则可110&10（6&4），若>0则取右孩子，<0则取左孩子。
4. 最终二分查找确定的值即为最后一个叶子节点，编号即为节点个数。

         1(1)
        /   \
    2(0)       3(1)
 /       \      /
4(0)     5(1)  6(0)

/**
 * 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===null){
        return 0
    }
    let level=0,temp=root.left
    while(temp){
        level++;
        temp=temp.left
    }
    let low=1<<level,high=(1<<level+1)-1,mid
    while(low<high){
        mid=Math.floor((high-low+1)/2)+low
        if(exits(root,level,mid)){
            low=mid
        }else{
            high=mid-1
        }
    }
    return low
};
function exits(root,level,k){
    let bit=1<<(level-1),temp=root
    while(bit){
        if(bit&k){
            temp=temp.right
        }else{
            temp=temp.left
        }
        bit=bit>>1
    }
    return temp!==null
}