二叉树——222. 完全二叉树的节点个数
1 题目描述
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。
2 题目示例
在这里插入图片描述
示例 2： 输入：root = [] 输出：0
示例 3： 输入：root = [1] 输出：1
3 题目提示
树中节点的数目范围是[0, 5 * 104] 0 <= Node.val <= 5 * 104 题目数据保证输入的树是 完全二叉树
4 思路
对于任意二叉树，都可以通过广度优先搜索或深度优先搜索计算节点个数，时间复杂度和空间复杂度都是O(n)，其中n是二叉树的节点个数。这道题规定了给出的是完全二叉树，因此可以利用完全二叉树的特性计算节点个数。 规定根节点位于第0层，完全二叉树的最大层数为h。根据完全二叉树的特性可知，完全二叉树的最左边的节点一定位于最底层，因此从根节点出发，每次访问左子节点，直到遇到叶子节点，该叶子节点即为完全二叉树的最左边的节点，经过的路径长度即为最大层数h。
在这里插入图片描述
具体做法是，根据节点个数范围的上下界得到当前需要判断的节点个数k，如果第k个节点存在，则节点个数一定大于或等于k，如果第k个节点不存在，则节点个数一定小于k，由此可以将查找的范围缩小—半，直到得到节点个数。 如何判断第k个节点是否存在呢?如果第k个节点位于第h层，则k的二进制表示包含h＋1位，其中最高位是1，其余各位从高到低表示从根节点到第k个节点的路径，О表示移动到左子节点，1表示移动到右子节点。通过位运算得到第k个节点对应的路径，判断该路径对应的节点是否存在，即可判断第k个节点是否存在。
在这里插入图片描述
5 我的答案
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;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
