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

原题(来源牛客网)

请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展开。此时有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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月27日
下一篇 2020年4月28日

相关推荐

  • leetcode374-猜数字大小

    原题 我们正在玩一个猜数字游戏。 游戏规则如下:我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了,我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接…

    算法 2019年12月31日
    0370
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04510
  • 剑指offer17-打印从1到最大的n位数

    原题(来源Leetcode) 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: …

    算法 2020年4月17日
    070
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250
  • 剑指offer50-第一个只出现一次的字符

    原题(来源Leetcode) 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s…

    算法 2020年6月10日
    0170
  • leetcode199-二叉树的右视图

    原题 给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出:&nb…

    算法 2020年4月22日
    0110
  • leetcode837-新21点

    原题 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏,描述如下: 爱丽丝以 0 分开始,并在她的得分少于 K 分时抽取数字。 抽取时,她从 [1, W] 的范围中随机获得一…

    算法 2020年6月3日
    0100
  • leetcode146-LRU缓存机制

    原题 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) -…

    算法 2020年5月25日
    0100
  • leetcode46-全排列

    原题 给定一个没有重复数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [   [1,2,3],   [1,3,…

    算法 2020年3月3日
    0170
  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190

发表回复

登录后才能评论