本文涉及到的二叉树题目 222：完全二叉树的节点个数
就是一道统计完全二叉树的节点个数，在力扣标注着 Easy，我想着速速解决战斗，看懂题解之后，迅速复制粘贴，结束任务！
没想到呀，这道题的题解都看不太懂呢！怎么一道完全二叉树的题还涉及到了二分法呢？怎么还有很多位运算呢？这官方的题解也太难看懂了！于是，在我苦心钻研之下，还是征服了它！
下面一起来征服一下这道题！！！
完全二叉树 – 概念
完全二叉树就是整个树从上到下从左到右一直添加节点，不存在断了的情况，我们就简单讲解几个例子，对于完全二叉树完整的概念，这里就不做多余的赘述了！
像上面这颗二叉树，就不是一颗完全二叉树，因为最下面一层，从左到右不是连续的，缺少了 6 的节点，即 3 的节点没有左节点，但是有右节点，所以这就不是一颗完全二叉树。
完全二叉树 – 性质
-
满二叉树其实是完全二叉树的一种特殊的情况，完全二叉树的最后一层不一定是满的，但是除了最后一层，上面的每一层也都是满的，所以每一层的节点个数也是固定的。
第 h 层节点个数 =
注：（ h从0开始计数 ） -
如果从上到下从左到右把每个节点都编号的话，那么：
第 h 层：最左边节点编号 = ，最右边节点编号 =
注：（ h从0开始计数 ）
从上面的图配合下面的描述，应该可以理解了完全二叉树的两个性质。这为我们后面解答这道题有更好的一个理解和铺垫。
完全二叉树节点个数 – 可以实现的算法思路
递归思路：这道题其实可以使用递归来做，用两个指针，一个一直向左走，一个一直向右走，来判断这颗树是不是一个满二叉，如果是，直接使用公式返回节点数量就行，如果不是，那么使用递归分别判断当前节点的左子树和右子树。 – 这种解法我们就不多赘述了，目前网上的资料大多数都是介绍这种，我们着重介绍一下下面的解法。二分法 + 位运算：实现的话，我们分成几个步骤来讲一下：
完全二叉树节点个数 – 二分法+位运算
- 首先，我们把整个二叉树的节点从上到下，从左到右编号，即下图：
- 然后，我们把所有编号用二进制来表示：
-
然后我们用
0表示向左走，用1表示向右走，此时我们发现二进制编号二叉树中，除去第一位数字，其他的bits就代表了根节点到当前节点的路径。仔细看下图，是不是橙色部分就是路径！！！
-
因为完全二叉树只有最后一层节点不一定是满的，然后我们就在最后一层节点中，利用二分法找到最后一个节点编号是多少，它的编号就代表了这一颗完全二叉树有多少个节点。
-
我们其实主要要实现一个判断一个节点是否存在的函数。
我们着重讲解一下这个实现的思路：
因为除去第一位，后面的 bits 就是路径，我们可以使用位运算取每一位，然后控制从根节点怎么往下走，最后看节点存在与否就行。
涉及到的位运算：1 << n = 2 ^ n
右移，就是把二进制所有位向右移动，然后左边缺少的补0，详细的讲解大家搜索一下！
🌰：比如我们判断编号为
11的节点是否存在，编号对应的二进制为1011，然后我们需要除了第一位的所有bits，我们首先用0100去和编号做与运算，这样就拿到了从根节点要先怎么走，0100 & 1011，那么第二位就是0，所以我们从根节点就要向左走，然后再拿下一位，把0100右移一位，那就变成了0010，再和1011做与运算，我们就知道下一步再怎么走，最后我们就拿到了到达编号11的路径就是011，意思就是先从根节点向左走，然后再向右走两次。下面是示意图：
// 判断一个节点（k）是否存在的函数
// root：根节点
// level：最后一层
// k：节点
const exists = (root, level, k) => {
// 除去第一位二进制数，然后需要看的位数，第 level 层需要看 2的(level-1)次方的位数
let bits = 1 << (level - 1);
let node = root;
// 当节点不为空，且还没有拿完后面的位数
while (node !== null && bits > 0) {
// 判断这一位是0 还是 1
if (!(bits & k)) {
// 0就往左走
node = node.left;
} else {
// 1就往右走
node = node.right;
}
// 然后右移一位，去拿下一位
bits >>= 1;
}
// 如果 node 最后不为空，那么这个节点就是存在的
return node !== null;
}
- 之后，我们就用一个 while 循环，一直从根节点往下走，找到最大深度，然后我们知道了最大深度之后，我们就知道了这一层的最左边节点和最右边节点的编号是多少，然后使用二分法在最后一层判断节点是否存在，直到找到最后一层的最后一个元素，该元素的编号就是二叉树的节点个数。
完整代码：
// 判断一个节点（k）是否存在的函数
// root：根节点
// level：最后一层
// k：节点
const exists = (root, level, k) => {
// 除去第一位二进制数，然后需要看的位数，第 level 层需要看 2的(level-1)次方的位数
let bits = 1 << (level - 1);
let node = root;
// 当节点不为空，且还没有拿完后面的位数
while (node !== null && bits > 0) {
// 判断这一位是0 还是 1
if (!(bits & k)) {
// 0就往左走
node = node.left;
} else {
// 1就往右走
node = node.right;
}
// 然后右移一位，去拿下一位
bits >>= 1;
}
// 如果 node 最后不为空，那么这个节点就是存在的
return node !== null;
}
var countNodes = function (root) {
if (root === null) {
return 0;
}
// 层数
let level = 0;
let node = root;
// 因为是完全二叉树，所以一直往左走，就是最大层数
while (node.left !== null) {
level++;
node = node.left;
}
// 第 level 层编号最小是 2的level次方，最大是2的(level+1)次方 - 1
let low = 1 << level, high = (1 << (level + 1)) - 1;
// 使用二分法找到最后一层的最后一个节点
while (low < high) {
const mid = Math.floor((high - low + 1) / 2) + low;
if (exists(root, level, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return low;
};
最后
最后我们这道题就讲解完了，第一次写这么长的文章，其实也不确定自己是否讲解清楚了，主要记录下自己研究完一道算法题之后，豁然开朗的那种心情，迫不及待分享的心情吧！如果还有疑问，我们可以在评论区或者私信我，交流下这道题。
如果能有人看到这里，看到最后，那么谢谢你！🙏
原文链接：https://juejin.cn/post/7349065708050268194 作者：lxdll
