折纸问题

面试题

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折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);
    }
}

生活被二叉树包围了兄弟们，^ _^