题目：一颗二叉树，最大深度为D，且所有叶子深度都一样们所有结点从上到下从左至右编号如图，在结点1放一个小球，往下落，每个节点开始都是关闭，当每次有小球下落到一个开关上时，状态都会改变，当小球下落到一个结点上的开关关闭时，则往左走，否则往右走，直到走到叶子结点
要求输入：叶子的深度D 小球的个数I
输出：第I个小球最终所在的叶子编码
案例：
4 2
3 4
输出：
12
7
思路：
1️⃣对于一个结点k，其左结点和右结点编号依次为：2k, 2k+1
2️⃣方法1：做一个足够大的数组s【】，用来表示小球经过之后的状态，刚开始全置为0，而后s[k] = !s[k];判断s[k]如果是1，则第一个小球下落的标号是k2，此时的s[1]为1，表示打开，第二个小球进来时，则s[k] = 0，直接掉落编号为2k+1，以此类推直到最后k>(最大标号)
3️⃣方法2（比1更方便，速度更快）：根据题目小球掉落的规律可以看出，只需要判断出题中给出的I是奇数还是偶数，当I为奇数时，是往左走的第（I+1）/2个小球；当I是偶数时，是往右走的第I/2个小球，实用与每个层数的小球的判定
代码为：
include<iostream>
include<string>
const int maxd = 20;
int s[1<<maxd]; //1<<maxd表示2^20，用来表示结点数
int main()
{
int D, I;
while(scanf("%d%d", &D, &I) != EOF)
{
memset(s,0,sizeof(s));
int k, n = (1<<D)-1; //（1<<D）-1表示的是最大结点数，2^D-1
for(int i=0; i<I; i++)
{
k = 1; //无论哪个小球的初始都是从1开始，k为结点的编号
for(;;)
{
s[k] = !s[k];
k = s[k]? k2:k2+1; //判断开关的状态，来判断小球落到哪个编号结点
if(k>n) break; //若k>n时则跳出
}
}
printf("%d\n", k/2); //最后输出“出界”之前的叶子编号
return 0;
}
}
对于方法二有如下做法：
while(scanf("%d%d", &D, &I) != EOF)
{
int k = 1;
for(int i= 0; i<D-1; i++) //对于每一层的变化
{
if(I%2)
{
k = k2; //第奇数个小球时，是往左走，编号为k2，的第(i+1)/2个小球，依次类推
I = (I+1)/2;
}
else
{
k = k2+1; //第偶数个小球时，往右走，编号为k2+1,的第I/2个小球，而后依次类推
I = I/2;
}
}
printf("%d\n", k);
}
