1633: 二叉树子树的结点数目
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:27
解决:18
题目描述
一棵具有n个结点,高度为h的二叉树,如果它的每个结点都与高度为h的满二叉树中序号为0~n-1的结点一一对应,则称该二叉树为完全二叉树(Complete Binary Tree)。
现在需要你帮忙解决的问题是,结点m所在的子树中一共包括多少个结点(包括该子树的根结点)。
例如,n = 6,m = 2时上图中的结点m所在子树中包括的结点有2,5,因此结点m的所在子树中共有2个结点。m = 0时上图中m所在子树共有6个结点。m = 1时所在子树共有3个结点。
现在需要你帮忙解决的问题是,结点m所在的子树中一共包括多少个结点(包括该子树的根结点)。
例如,n = 6,m = 2时上图中的结点m所在子树中包括的结点有2,5,因此结点m的所在子树中共有2个结点。m = 0时上图中m所在子树共有6个结点。m = 1时所在子树共有3个结点。
输入
输入有多组。每组一行数据,包括两个整数m,n (0 <= m <= n <= 10000)。n表示完全二叉树的结点总数,m是要求的那棵子树的根结点的序号。最后一组测试数据中包括两个0,表示输入的结束。
输出
对于每一组测试数据,输出一行,该行包含一个整数,给出结点m所在子树中包括的结点的数目。
样例输入 复制
2 7
141 6574
1 754
0 0
样例输出 复制
3
63
498