二叉树中序遍历-折纸问题

原题(来源牛客网)

请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展开。此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折,对折N次。请从上到下计算出所有折痕的⽅向。

给定折的次数n,请返回从上到下的折痕的数组,若为下折痕则对应元素为"down",若为上折痕则为"up".

示例:

输入: 1
输出: ["down"]

解法

思想

每一次折叠,会在现有折痕的上方产生一个下的折痕,在折痕的下方产生一个上的折痕。(可以动手尝试理解)

这样就会形成一个二叉树:

二叉树中序遍历-折纸问题

从纸的上面到下面打印就是二叉树的 RVL 的遍历(右根左,特殊的中序遍历)。

代码

import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        List<String> result = new ArrayList<>();
        fold(1, n, "down", result);
        return result.toArray(new String[result.size()]);
    }
    private static void fold(int level, int n, String type, List<String> result){
        if (level <= n) {
            fold(level + 1, n, "down", result);
            result.add(type);
            fold(level + 1, n, "up", result);
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e4%ba%8c%e5%8f%89%e6%a0%91%e4%b8%ad%e5%ba%8f%e9%81%8d%e5%8e%86-%e6%8a%98%e7%ba%b8%e9%97%ae%e9%a2%98/