从左神视频上看到一个有趣的题目,据说是微软的算法面试题:一个长纸条,对折后再展开,中间会有一个凹痕,然后同样的方式,再继续对折, 又会多出2条折痕(不过新折痕会有凸有凹),如此反复对折,纸条上就会留下一系列的折痕,见下图:
要求:输入1个数字(n),表示对折的次数, 从上而下, 打印每1条拆痕的类型(即:凹痕?凸痕?)
思路:咋一看, 好象无从下手, 但是参考上图中的标记,尝试几次后,把这些痕迹画成一颗二叉树,纸条从上到向的痕迹类型,正好是中序遍历!不得不感叹这题出得巧妙
找到规律后,就好办了,不过题目只要求打印节点值,并不需要根正建立一颗二叉树,而且观察上图, 可以发现每个节点的左子节点,全是“凹”,右子节点全是“凸”, 所以代码可以精减些:
/**
* 打印折痕
* @param level 当前层序号(根节点层序为1)
* @param maxLevel 总层数(即:对折次数)
* @param bulge 本层痕迹是否为“凸”痕
*/
static void printFolder(int level, int maxLevel, boolean bulge) {
if (level > maxLevel) {
return;
}
//分析发现,左侧全是凹痕
printFolder(level + 1, maxLevel, false);
//递归序第2次打印时机,正好对应中序遍历
System.out.printf(level + "" + (bulge ? "凸\t" : "凹\t"));
//分析发现,右侧全是凸痕
printFolder(level + 1, maxLevel, true);
}
调用时(假设对折3次):
printFolder(1, 3, false);
输出:
3凹 2凹 3凸 1凹 3凹 2凸 3凸