题目描述
小红有一棵包含 n个节点的完全二叉树[1]，其中 1号节点为根，i号节点的左儿子编号是 2×i，右儿子编号是 2×i+1。
现在有 q次询问，每次查询一个 x，你需要回答与 x号节点深度[3]相同的节点有多少个（包含 x本身）。
【名词解释】
完全二叉树[1]：
满足以下全部条件的二
展开全文
二叉树每层的节点个数为：1，2，4，8，16，32...
二叉树每层最后一个节点编号：1，3，7，15，31，63...
输入节点数后，开一个map数组，分别记录每层的节点总数及最后一个节点编号，然后遍历map数组，直到找到查询的节点编号小于等于某一层最后一个节点时，输出这层的节点总数。
```#i
展开全文
要求我求出与某编号的深度相同的有几个，除了最后一行，其他都是满的。然后我们观察完全二叉树其实是有规律的，第n层的最后一个编号是（2的n次方 - 1），比如第二层最后一个是3，然后这题又给你最后的编号a了，只要当2的n次方 - 1大于它时（另外这题其实最后一行一定是不满的），然后就是a-2的（n次方-
展开全文
解题思路：通过分析题目得到x∈[2^（i-1）,2^i),并发现每层的节点个数就是那一层的第一个数。（i是x所在层数）
此时x分为两种情况：一种是x不在最后一层，那么只要找到x的层数直接输出2^(i-1)就可以了。
另一种是x在最后一层，最后一层的个数是n-2^(i-1)+1。
解题代码：
由完全二叉树的性质可知，树的总深度g(n)，除了最后一层，第i层的节点个数为2的i-1次方，当层数为i时，深度j为i-1,即深度
j的节点个数为2的j次方。
要判断与x号节点深度相同的节点数量，只需要判断x的深度high。
若x不在最后一层，则与x号节点深度相同的节点数量为2的high
次方；
若x
展开全文
题目大概意思就是1到n的节点依次排列成二叉树，根据题目画图，我是根据给的询问节点编号依次除二得到深度，最后特判一下可能没填满的情况
#include <bits/stdc++.h>
using namespace std;
int main(){
lon
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
