大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一颗二叉树，求出该树的节点个数。”
2、题目描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1： 输入： root = [1,2,3,4,5,6] 输出： 6
示例 2： 输入： root = [] 输出： 0
二、解题
1、思路分析
题意要求给定一个完全二叉树，求出该数的节点个数。
对于任意二叉树，都可以通过广度优先搜索算法BFS计算节点个数，这道题给定的完全二叉树，可以使用完全二叉树的特点计算节点个数。
完全二叉树的特性可知，最左边的节点一定位于最底层，从根节点出发，每次访问左子节点，直到遇到叶子结点，该叶子结点即为完全二叉树的最左边的节点，经过的路径啊成都为最大层数h。
第i层包含2i个节点，最底层包含的节点数最少为1，最多为2h。
因此对于最大层数为h的完全二叉树，可以通过二分查找的方式得到完全二叉树的节点个数。
根据节点的个数范围判断得到节点个数k：
- 如果第k个节点存在，则节点个数一定大于或等于k
- 如果第k个节点不存在，可以将查找的范围缩小一半，直到得到节点个数
2、代码实现
代码参考：
class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int level = 0; TreeNode node = root; while (node.left != null) { level++; node = node.left; } int low = 1 << level, high = (1 << (level + 1)) - 1; while (low < high) { int mid = (high - low + 1) / 2 + low; if (exists(root, level, mid)) { low = mid; } else { high = mid - 1; } } return low; } public boolean exists(TreeNode root, int level, int k) { int bits = 1 << (level - 1); TreeNode node = root; while (node != null && bits > 0) { if ((bits & k) == 0) { node = node.left; } else { node = node.right; } bits >>= 1; } return node != null; } }
3、时间复杂度
时间复杂度：O(log2 n)
其中n是完全二叉树的节点数。
空间复杂度：O(1)
只需要常数级的变量空间。
三、总结
在判断第k个节点是否存在的时候，用到了位运算得到第k个节点对应的路径，判断路径是否存在，就可以判断第k个节点是否存在。
比如说第k个节点位于第h层，则k的二进制表示包含h+1位，其中最高位是1，其余各位从高到底表示根节点到第k个节点的路径。
0表示移动左子节点，1表示移动到右子节点：
