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

原题(来源牛客网)

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

相关推荐

  • leetcode236-二叉树的最近公共祖先

    原题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 …

    2020年1月15日
    060
  • 剑指offer40-最小的k个数

    原题(来源Leetcode) 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。 示例 1: …

    算法 2020年3月20日
    0380
  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • leetcode99-恢复二叉搜索树

    原题 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例 1: 输入: [1,3,null,null,2]    1 …

    算法 2020年3月1日
    070
  • leetcode435-无重叠区间

    原题 给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”,但没…

    算法 2020年2月18日
    02420
  • leetcode496-下一个更大元素I

    原题 给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。 nums…

    算法 2020年1月31日
    0380
  • leetcode94-二叉树的中序遍历

    原题 给定一个二叉树,返回它的 中序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2019年12月12日
    01120
  • leetcode135-分发糖果

    原题 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 你需要按照以下要求,帮助老师给这些孩子分发糖果: 每个孩子至少分配到 1 个…

    算法 2020年2月17日
    060
  • leetcode18-四数之和

    原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 ta…

    算法 2020年5月5日
    0120
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    090

发表回复

登录后才能评论