二叉树经典问题--折纸问题_力扣 二叉树 折纸问题

二叉树经典问题–折纸问题
请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。
实现

public class PagerFoldingTest {
    public static void main(String[] args) {
        Node<String> tree=createTree(2);
        printTree(tree);
    }
    public static Node<String> createTree(int N){
        Node<String> root=null;
        for (int i = 0; i < N; i++) {
            if(i==0){
                root=new Node<String>("down",null,null);
                continue;
            }
            MyQueue<Node> queue = new MyQueue<Node>();
            queue.enqueue(root);
            while(!queue.isEmpty()){
                Node tmp = queue.dequeue();
                if(tmp.left!=null){
                    queue.enqueue(tmp.left);
                }
                if(tmp.right!=null){
                    queue.enqueue(tmp.right);
                }
                if(tmp.left==null&&tmp.right==null){
                    tmp.left=new Node("down",null,null);
                    tmp.right=new Node("up",null,null);
                }
            }
        }
        return root;
    }
    public static void printTree(Node<String> root){
        if(root==null){
            return ;
        }
        if(root.left!=null){
            printTree(root.left);
        }
        System.out.print(root.item+" ");
        if(root.right!=null){
            printTree(root.right);
        }
    }
    public static class Node<T>{
        public T item;
        public Node left;
        public Node right;

        public Node(T item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54