zcmu-4928: 二叉树
4928: 二叉树
Time Limit: 1 Sec Memory Limit: 32 MB
Submit: 24 Solved: 17
[Submit][Status][Web Board]Description
![]()
如上所示,由正整数1,2,3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是,结点m所在的子树中一共包括多少个结点。
比如,n = 12,m = 3那么上图中的结点13,14,15以及后面的结点都是不存在的,结点m所在子树中包括的结点有3,6,7,12,因此结点m的所在子树*有4个结点。Input
输入数据包括多行,每行给出一组测试数据,包括两个整数m,n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0,表示输入的结束,这组数据不用处理。
Output
对于每一组测试数据,输出一行,该行包含一个整数,给出结点m所在子树中包括的结点的数目。
Sample Input
3 7 142 6574 2 754 0 0
Sample Output
3 63 498
HINT
Source
节点x所在子树是以他为root的子树,比如x = 5,y= 11则子树为~~
每一层的节点数 = 层数 * 2,左子树 = 父节点 * 2,右子树 = 父节点 * 2 + 1,
所以从 以x节点为root的左右子树开始遍历(所以root自己也要算做一点),一直到右子树的位置>= y,所求的节点个数就是加上右子树的位置>= y前每一层的所有的节点个数,
举例:x = 3,y = 14,子树为,
(1) left = 6,r = 7,t = 2,ans = 1 + 2,
(2) left = 12, r = 15,t = 4,(r >= y 了,所以break,ans没有加上这一层所有的节点)
所以再判断下,加上下一行的几个节点~
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
int x,y;
while(scanf("%d%d",&x,&y) && x && y)
{
int left = 2 * x;
int right = 2 * x + 1;
int t = 1;
int ans = 1;//自己也算做一点
while(right <= y)//遍历每一层,直到最后一个节点
{
t *= 2;//每一层的节点数
ans += t;
left *= 2;//左孩子所在节点序号
right = right * 2 + 1;//右孩子所在节点序号
}
if(left <= y) ans += y - left + 1;
cout<<ans<<endl;
}
return 0;
}