请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。请从上到下打印所有折痕的方向。
例如:N=1时，打印: down N=2时，打印: down down up
不难发现，每次对折后，都有这样一个规律：在已有的折痕上边都是凹折痕，下边都是凸折痕，所以从上到下打印所有折痕方向，就是在中序遍历二叉树。
那么需要把这颗树完整建出来吗？对折N次，就会有 N^(2-1)条折痕，然后准备一个长度为 N^(2-1)的数组，再将数组填满，最后再将数组打印出来，这种实现方式巨大的浪费空间，肯定有更优的解决办法——用递归模拟整棵树，因为这颗树有着明确的规则，所以不用把所有结点建出来才能够打印。
- 整棵树的头结点是“凹”
- 所有左子树的头结点是“凹”，所有右子树头结点是“凸”
这种方式的时间复杂度就是递归栈的代价，O(N)
package com.harrison.class07; public class Code08_PaperFloding { public static void printAllFolds(int N) { printProcess(1, N, true); } // i 节点层数 // N 一共要打印的层数，在题中就是对折的次数 // down==true --> 凹 up==false --> 凸 public static void printProcess(int i, int N, boolean down) { if (i > N) { return; } printProcess(i + 1, N, true); System.out.println(down ? "凹" : "凸"); printProcess(i + 1, N, false); } public static void main(String[] args) { int N = 3; printAllFolds(N); } }
