折纸问题.

请把一张纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕展开，此时折痕是凹下去的，即折痕突起的方向指向纸条的背面，如果从纸条的下边向上方连续对拆次，压出的折痕后展开 此时有三条折痕，从上到下依次是下折痕，下折痕和上折痕 。给定一个输入参数N 代表纸条都从下边向上方连续对折N次 请从上到下打印所有折痕的方向
示例 1
输入1
输了
[“down”]
示例2
输入2
输入出
[“down”,”down”,”up”]

一开始看的时候，觉得应该是找规律。。
后面枚举了几轮之后，发现有点接近“树“的数据结构
本题解正是循着这种思路做的

public class Node {
    Node right;
    Node parent;
    String value;
    public Node(String value){
        this.value = value;
    }
}

import java.util.*;



public class ZheZhi {

    static int n;
    static Node starter;
    static List ans = new ArrayList<>();

    final static String DOWN = "down";
    final static String UP = "up";

    
    static void init(){
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        scanner.close();
    }

    static void zheZhi(){
        //队列记录新产生的折痕节点
        LinkedList adds = new LinkedList<>();
        //折纸的次数
        for(int i=1;i<=n;i++){
             if(i==1){
                 Node root = new Node(DOWN);
                 starter = root;
                 adds.offer(root);
                 continue;
             }

             //每次遍历一层，可以确定一次最左侧的节点
             starter = null;

             int size = adds.size();

             while(true){

                if(size-- <= 0){
                    break;
                }

                Node node = adds.pollFirst();
                if(node == null){
                    break;
                }

                Node left = new Node(DOWN);
                Node right = new Node(UP);

                left.parent = node;
                node.right = right;

                adds.offerLast(left);
                adds.offerLast(right);

                 //控制最左侧节点
                if(starter == null){
                    starter = left;
                }
             }
        }
    }

    static void out(Node node){
        ans.add(node.value);
        if(node.parent != null && node.right == null){
            out(node.parent);
        }
        else if(node.parent != null && node.right != null){
            out(node.right);
            out(node.parent);
        }
        else if(node.parent == null && node.right != null){
            out(node.right);
        }
    }

    public static void main(String[] args) {
        init();
        zheZhi();
        out(starter);
        System.out.println(ans);
    }
}