折纸问题

import java.util.Scanner;

public class Main{





    //创建树
    public static Node<String> createTree(Node<String> root,int n){        //创建一棵以root为根结点，深度为n的树,返回树的根结点
        //如果n=2，则构建左右子树并退出递归
        if (n==2) {
            //创建树的根结点
            //Node<String> root = new Node("down", null, null);
            root.left=new Node("down", null, null);
            root.right=new Node("up", null, null);
            return root;
        }else if(n>2){
            //创建树的根结点
            //Node<String> root = new Node("down", null, null);
            //创建树的左子树，并让根结点指向左子树
            root.left=new Node("down", null, null);
            root.right=new Node("up", null, null);
            root.left = createTree(root.left,n - 1);
            //创建树的右子树，并让根结点指向右子树
            root.right = createTree(root.right,n - 1);
            return root;
        }
        return root;
    }

    //打印输出
    public  static void printTree(Node<String> x) {
        if (x == null) {
            return;
        }
        if (x.left!=null){
            printTree(x.left);
        }
        System.out.println(x.item);
        if (x.right!=null){
            printTree(x.right);
        }
    }

    //主方法
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        Node<String> root=new Node<>("down",null, null);//根结点
        Node<String> tree=createTree(root,N);
        printTree(root);

    }

    private static class Node<T> {
        //存储结点值
        private T item;
        //存储左孩子结点
        private Node left;
        //存储右孩子结点
        private Node right;
        //构造方法

        public Node(T item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}

递归中序遍历
import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        
        List<String> list = new LinkedList<String>();
        listProcess(1,n,true,list);
        int len = (2<< n-1) -1;
        String[] strs = new String[len];
        for(int i=0; i<len; i++){
            strs[i] = list.get(i);
        }
        
        return strs;
    }
    
    public void listProcess(int i, int n, boolean isDown, List<String> list){
        if(i>n){
            return;
        }
        listProcess(i+1,n,true,list);
        list.add(isDown?"down":"up");
        listProcess(i+1,n,false,list);
    }
}