一道简单的完全二叉树算法,我竟然做了好久?

本文涉及到的二叉树题目 222:完全二叉树的节点个数

就是一道统计完全二叉树的节点个数,在力扣标注着 Easy,我想着速速解决战斗,看懂题解之后,迅速复制粘贴,结束任务!

没想到呀,这道题的题解都看不太懂呢!怎么一道完全二叉树的题还涉及到了二分法呢?怎么还有很多位运算呢?这官方的题解也太难看懂了!于是,在我苦心钻研之下,还是征服了它!

下面一起来征服一下这道题!!!

完全二叉树 – 概念

完全二叉树就是整个树从上到下从左到右一直添加节点,不存在断了的情况,我们就简单讲解几个例子,对于完全二叉树完整的概念,这里就不做多余的赘述了!

一道简单的完全二叉树算法,我竟然做了好久?

像上面这颗二叉树,就不是一颗完全二叉树,因为最下面一层,从左到右不是连续的,缺少了 6 的节点,即 3 的节点没有左节点,但是有右节点,所以这就不是一颗完全二叉树。

完全二叉树 – 性质

一道简单的完全二叉树算法,我竟然做了好久?

  1. 满二叉树其实是完全二叉树的一种特殊的情况,完全二叉树的最后一层不一定是满的,但是除了最后一层,上面的每一层也都是满的,所以每一层的节点个数也是固定的。

    第 h 层节点个数 =

    2h2^h

    注:( h从0开始计数 )

  2. 如果从上到下从左到右把每个节点都编号的话,那么:

    第 h 层:最左边节点编号 =

    2h2^h

    ,最右边节点编号 =

    2(h+1)12^(h+1) – 1

    注:( h从0开始计数 )

从上面的图配合下面的描述,应该可以理解了完全二叉树的两个性质。这为我们后面解答这道题有更好的一个理解和铺垫。

完全二叉树节点个数 – 可以实现的算法思路

  1. 递归思路:这道题其实可以使用递归来做,用两个指针,一个一直向左走,一个一直向右走,来判断这颗树是不是一个满二叉,如果是,直接使用公式返回节点数量就行,如果不是,那么使用递归分别判断当前节点的左子树和右子树。 – 这种解法我们就不多赘述了,目前网上的资料大多数都是介绍这种,我们着重介绍一下下面的解法。
  2. 二分法 + 位运算:实现的话,我们分成几个步骤来讲一下:

完全二叉树节点个数 – 二分法+位运算

  1. 首先,我们把整个二叉树的节点从上到下,从左到右编号,即下图:

一道简单的完全二叉树算法,我竟然做了好久?

  1. 然后,我们把所有编号用二进制来表示:

一道简单的完全二叉树算法,我竟然做了好久?

  1. 然后我们用 0 表示向左走,用 1 表示向右走,此时我们发现 二进制编号二叉树 中,除去第一位数字,其他的 bits 就代表了根节点到当前节点的路径。

    仔细看下图,是不是橙色部分就是路径!!!

一道简单的完全二叉树算法,我竟然做了好久?

  1. 因为完全二叉树只有最后一层节点不一定是满的,然后我们就在最后一层节点中,利用二分法找到最后一个节点编号是多少,它的编号就代表了这一颗完全二叉树有多少个节点。

  2. 我们其实主要要实现一个判断一个节点是否存在的函数。

    我们着重讲解一下这个实现的思路:

    因为除去第一位,后面的 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;
}
  1. 之后,我们就用一个 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

(0)
上一篇 2024年3月23日 下午4:23
下一篇 2024年3月23日 下午4:33

相关推荐

发表评论

登录后才能评论