折纸的折痕（RVL中序遍历）

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

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

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

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

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

从纸的上面到下面打印就是二叉树的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