本文涉及到的二叉树题目 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