算法练习(13)-打印纸条对折的折痕类型（凹痕?凸痕？）

从左神视频上看到一个有趣的题目，据说是微软的算法面试题：一个长纸条，对折后再展开，中间会有一个凹痕，然后同样的方式，再继续对折， 又会多出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 ? "凸	" : "凹	"));
        //分析发现，右侧全是凸痕
        printFolder(level + 1, maxLevel, true);
    }

调用时（假设对折3次）：

printFolder(1, 3, false);

输出：

3凹 2凹 3凸 1凹 3凹 2凸 3凸