有一幅二叉树， 最大深度为D. 且所有叶子的深度都相同. 所有结点从上到下从左到
右编号为1，2，3.….2D- l . 在结点1 有一个小球，它会往下落. 每个内结点上都有一个开
关，初始全部关闭，当每在有小球落到个开关上时， 开关都会改变. 当小球到这一
个内结点时.如果该结点上的开夫先闭， 贝小球往左走， 否则往右走，直到走到叶子结点， 如
图6-8 所示.
一些小球从结点1 处佳次开始下落，最后一个小草将会落到哪里?输入叶子深度D
右编号为1，2，3.….2D- l . 在结点1 有一个小球，它会往下落. 每个内结点上都有一个开
关，初始全部关闭，当每在有小球落到个开关上时， 开关都会改变. 当小球到这一
个内结点时.如果该结点上的开夫先闭， 贝小球往左走， 否则往右走，直到走到叶子结点， 如
图6-8 所示.
一些小球从结点1 处佳次开始下落，最后一个小草将会落到哪里?输入叶子深度D
和小球个N数输出第N 个小球最后所在的叶子编号.
这道题的关键就在于对于一个节点K，左孩子是2N，右孩子是2N+1。
import java.util.Scanner;
public class N {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int deep, num;
while (true) {
//输入二叉树的深度
deep = sc.nextInt();
//输入小球的个数
num = sc.nextInt();
boolean[] s = new boolean[1 << deep];
//8 << n的值为8*（2^n）
int MAX = (1 << deep) - 1;
for (int i = 1; i <= num; i++) {
int end = 1;
while (true) {
if (s[end] == false) {
s[end] = true;
end = end * 2;// 关键 左孩子是2N，右孩子是2N+1
} else {
s[end] = false;
end = end * 2 + 1;
}
if (end > MAX) {
break;
}
}
if (i == num) {
System.out.println(end / 2);
}
}
}
}
}
这种算法利用了一个数组s，但是我们可以发现，这个数组可能会有2^D-1大小，所以我们可以考虑另一种算法。
每个小球都会落在根节点上，因此开始的两个小球必然是一个在左子树，一个在右子树。一般的，只需看小球的奇偶性，就能知道他是最终停在哪颗子树上，对于那些落入根节点左子树的小球来说，只需知道该小球是第几个落在根的左子树里的，就可以知道他下一步往左还是往右了，以此类推，直到小球落在叶子上。
当小球个数num是奇数时，他是往左走的第（num+1）/2个小球，当num是偶数时，他是往右走的第num/2个小球，这样我们可以直接模拟最后一个小球的路线。
import java.util.Scanner;
public class N {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int deep, num;
while (true) {
// 输入二叉树的深度
deep = sc.nextInt();
// 输入小球的个数
num = sc.nextInt();
int end = 1;
for (int j = 0; j < deep - 1; j++) {
if (num % 2 == 1) {
end = end * 2;
num = (num + 1) / 2;
} else {
end = end * 2 + 1;
num = num / 2;
}
}
System.out.println(end);
}
}
}
