折纸问题
面试题
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。 如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。
给定一个输入参数N，代表纸条都从下边向上方连续对折N次。 请从上到下打印所有折痕的方向。
例如:N=1时，打印: down N=2时，打印: down down up
折纸演示
这样，从下往上折
image-20210223093803217.png
image-20210223093830087.png
思考
一生二，二生四，这是啥，是不是马上想到二叉树，而且还是满二叉树，把这个图片左旋90°，然后整理整理就是下面的树。
第一次折
①凹
第二次折
image-20210223094451620.png
第三次折
image-20210223094517693.png
题目里把凹折痕说是下折痕(down)，凸折痕(up)，你可以发现纸条从上到下正好就是这个满二叉树的中序遍历。
那么题解就是输出这个满二叉树的中序遍历，那如何操作呢？需要把树建出来，然后再用树头节点来输出么？由于左孩子节点都是凹折痕，右孩子都是凸折痕，树是满树，也就是说我们不需要知道每个节点的具体结构内存位置啥的。只要知道是左右孩子我就输出down或者up，然后有多少层我就递归多少层就完事了。
代码实现
public class Code08_PaperFolding {
public static void printPaperFoldingMark(int N){
ins(N,1,true);
}
private static void ins(int n, int floor, boolean down) {
if(floor>n) return;
ins(n,floor+1,true);
System.out.print((down?"down":" up ")+"\t");
ins(n,floor+1,false);
}
public static void main(String[] args) {
printPaperFoldingMark(3);
}
}
生活被二叉树包围了兄弟们，^ _^
