折纸的折痕(RVL中序遍历)

举报
兔老大 发表于 2021/04/21 23:05:01 2021/04/21
2.3k+ 0 0
【摘要】 这个题我见到过不止一次。笔试面试。 你拿个纸折一折会发现是这样的: 这棵树左子树是纸的下半部分,右子树是纸的上半部分。 下折痕指的是折痕突起的方向是纸的背面。 可以看出折痕是一棵满二叉树,根节点是下折痕,每一棵子树的左孩子是上折痕,每一棵子树的右孩子是下折痕。 从纸的上面到下面打印就是二叉树的RVL(右根左)的遍历。 对折N次就是指N层节点。 /** *...

这个题我见到过不止一次。笔试面试。

你拿个纸折一折会发现是这样的:

这棵树左子树是纸的下半部分,右子树是纸的上半部分。

下折痕指的是折痕突起的方向是纸的背面。

可以看出折痕是一棵满二叉树,根节点是下折痕,每一棵子树的左孩子是上折痕,每一棵子树的右孩子是下折痕。

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

对折N次就是指N层节点。


      /**
       * 请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展开。
       * 此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;
       * 突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折,
       * 对折N次。请从上到下计算出所有折痕的⽅向。
       * 给定折的次数n,请返回从上到下的折痕的数组,若为下折痕则对应元素为"down",
       * 若为上折痕则为"up".
       * <p>
       * 从纸的上面到下面打印就是二叉树的RVL(右根左)的遍历。
       *
       * @param n
       * @return
       */
      public static 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) {
      //R
       fold(level + 1, n, "down", result);
      //V
       result.add(type);
      //L
       fold(level + 1, n, "up", result);
       }
      }
  
 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/104037475

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。