AlgoPressAppearance
0222-完全二叉树的节点个数
https://leetcode.cn/problems/count-complete-tree-nodes
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6]
输出：6
示例 2：
输入：root = []
输出：0
示例 3：
输入：root = [1]
输出：1
提示：
- 树中节点的数目范围是[0, 5 * 10^4]
- 0 <= Node.val <= 5 * 10^4
- 题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
思路1：遍历统计个数
csharp
public class Solution {
int count = 0;
private void dfs(TreeNode cur){
if(cur == null){
return;
}
count++;
dfs(cur.left);
dfs(cur.right);
}
public int CountNodes(TreeNode root) {
dfs(root);
return count;
}
}
思路2：完全二叉树定义
根据完全二叉树的性质，往右一直遍历得到层数，至倒数第二层肯定是填满的。 第一层的编号是 2^0 = 1 第二层的编号是 2^1 = 2, 3 第三层的编号是 2^2 = 4, 5, 6, 7 第四层的编号是 2^3 = 8, 9, 10, 11, 12, 13, 14, 15 比如要判断节点 9 是否存在，因为第四行从 8=1000开始的，每个开始的位都一样，后面分别是 000,001,010,011,100,101,110,111 而0和1刚好是上面节点往左节点或往右节点的方向。 比如 000，表示上面的三个节点都是往左 , 001, 表示从根节点开始 两次往左，一次往右。
我们首先判断出层数，找到最后一层，然后依次从中间开始，使用二分查找大，判断最后节点的位置 比如第四层 8,15的中间位置 是 (8 + 15)/2 = 11, 二进制编码是 1011 ，我们就判断从根节点 往左，往右，往右，然后看那个节点是否存在。 存在就不用判断左边，不存在就不用判断右边。
然后找到最终节点。
csharp
public 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 left = 1 << level; //左边界
int right = (1 << (level+1)) - 1 ; //右边界
while(left < right){
int mid = left + (right-left+1)/2;
if(Exist(root,level,mid)){ //在右边
left = mid;
}
else{ //在左边
right = mid - 1;
}
}
//最后结果就是 left
return left;
}
private bool Exist(TreeNode root, int level, int n){
int bits = 1 << (level - 1);
TreeNode node = root;
while(node != null && bits > 0){
if( (bits & n) == 0){
node = node.left;
}
else{
node = node.right;
}
bits >>= 1;
}
return node != null;
}
}