程序员社区

算法题-二叉树的递归套路-折纸问题

算法题-二叉树的递归套路-折纸问题

题目
请把一段纸条竖着放在桌子上,然后从纸条的下边向上方对折1次,压出折痕后展开。此时折痕是凹下去的,即折痕突起的方向指向纸条的背面。

如果从纸条的下边向.上方连续对折2次,压出折痕后展开,此时有三条折痕,从上到下依次是下折痕、下折痕和上折痕。

给定一个输入参数N,代表纸条都从下边向.上方连续对折N次。请从上到下打印所有折痕的方向。

例如:

N=1时,打印: down

算法题-二叉树的递归套路-折纸问题插图
image-20210630095045214

N=2时,打印: down down up

算法题-二叉树的递归套路-折纸问题插图1
image-20210630095127406

考察的是二叉树的中序遍历,可以试着折两下子,发现每一次折都会在最新的折痕上下位置出现两个新的折痕,一上一下,上为down,下为up。打印的时候,从上往下打印,类似于二叉树的中序遍历。

算法题-二叉树的递归套路-折纸问题插图2
image-20210630095348229
public class Code07_PaperFolding {

    public static void printAllFolds(int N) {
        process(1, N, true);
        System.out.println();
    }

    // 当前你来了一个节点,脑海中想象的!
    // 这个节点在第i层,一共有N层,N固定不变的
    // 这个节点如果是凹的话,down = T
    // 这个节点如果是凸的话,down = F
    // 函数的功能:中序打印以你想象的节点为头的整棵树!
    public static void process(int i, int N, boolean down) {
        if (i > N) {
            return;
        }
        process(i + 1, N, true);
        System.out.print(down ? "凹 " : "凸 ");
        process(i + 1, N, false);
    }

    public static void main(String[] args) {
        int N = 4;
        printAllFolds(N);
    }
}

RUN> ?????????

凹 凹 凸 凹 凹 凸 凸 凹 凹 凹 凸 凸 凹 凸 凸
赞(0) 打赏
未经允许不得转载:IDEA激活码 » 算法题-二叉树的递归套路-折纸问题

一个分享Java & Python知识的社区