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

示例 1：

 

 

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

    树中节点的数目范围是[0, 5 * 104]
    0 <= Node.val <= 5 * 104
    题目数据保证输入的树是 完全二叉树

 

思想:不对二叉树进行全部遍历,要充分利用完全二叉树的特性,实际上就是对最后一层的叶子结点判定个数,我们可以对二叉树的所有结点进行二分查找来实现。

首先引入位运算的概念,我们将最后一层的叶子结点按照完全二叉树的顺序进行编号,令根节点为第0层开始,设二叉树层数level=h,那么最后一层的叶子结点编号范围为[2^h~2^h+1-1]。

比如示例1中的图,最底层从4开始到6二进制表示分别为 100 101 110,从根节点到最底层(第三层),我们需要提取他们的后两位来表示路径,0表示向左,1表示向右,如4可以表示为0和0,从根节点出发,向左,再向左。那么我们设定一个参数来逐个提取这个路径信息——bits，bits初始大小设置为2^h-1大小,如示例1中bits设为2即010,每次提取路径后,bits都向右一位处理以便提取下一个路径。

我们使用go中sort库的search函数实现自带的二分查找。先遍历出二叉树的层数，初始总的值假定他为一个满二叉树，即2^h+1个节点,示例1中level = 2 ,初始假设节点为个,取中值为4,判断4这个点是否在最后一层,和2^h判断,发现相等,继续比较,bits=2,4和bits按位与后得到0,则表示向左,node = node.Left,bits整体右移1位提取下一位路径,4再与1按位与得到0,即再向左node = node.Left。此时bits再向右一位为0，判断结束，node指向的存在的结点。则修改二分查找中的起始位置为中点，查找6~8这个范围。继续循环，直到找到一个编号的结点是空结点，返回这个空编号前一个编号即可。

func countNodes(root *TreeNode) int {
	if root ==nil{
		return 0
	}
	level :=0
	for node:=root;node!=nil;node = node.Left{
		level++
	}
	return sort.Search(1<<(level+1),func(k int)bool{
		//如果k不在最后一层 返回false
		if k <=1<<level{
			return false
		}
		//bits 的值取比最高层表示的数低一位的数 比如最高层第一个数是100 bits应该取010 从第二位开始读
		bits:= 1<<(level-1)
		node:=root
		for node!=nil&&bits>0{
			if bits&k>0{
				node = node.Left
			}else{
				node = node.Right
			}
			bits >>=1
		}
		return node == nil
	})-1
}

题目来源：https://leetcode-cn.com/problems/count-complete-tree-nodes