문제 // 자료구조 // 트리(Tree) // 깊이리스트 // toJava

/**
 * [깊이의리스트]
 *  이진트리가 주어졌을때, 같은 깊이에 있는 노드를 연결리스트로 연결해 주는 알고리즘
 *  즉, 트리의 깊이가 D라면 D개의 연결리스트를 만들어라
 *
 * [풀이]
 *  => 트리가 주어지냐 ?
 *  => D라는 것을 매개변수로 받아야 하냐 ?
 *  => 큐를 사용해도 되냐 (너비우선탐색) ?
 *
 * */
public class Q03 {

    /* Main */
    public static void main(String[] args) {

        // @Test
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        // == 각개비교 ==
        List<Integer> level1 = getElementsByTreeLevel(1, root);
        System.out.println(Arrays.toString(level1.toArray(new Integer[level1.size()])));
        List<Integer> level2 =getElementsByTreeLevel(2, root);
        System.out.println(Arrays.toString(level2.toArray(new Integer[level2.size()])));
        List<Integer> level3 =getElementsByTreeLevel(3, root);
        System.out.println(Arrays.toString(level3.toArray(new Integer[level3.size()])));

        // == 전체비교 ==
        ArrayList<LinkedList<Node>> allLevel = createLevelLinkedList(root);
        for (int i = 0; i < allLevel.size(); i++) {
            for (int j = 0; j < allLevel.get(i).size(); j++)
                System.out.printf(allLevel.get(i).get(j).data + " ");
            System.out.println();
        }
    }

    /* Node */
    static class Node {
        int data;
        Node left;
        Node right;
        public Node(int data) {
            this.data = data;
        }
    }

    /* getElementsByTreeLevel - 라인을 매개변수로 받아 반환하기 */
    public static List<Integer> getElementsByTreeLevel(int level, Node root) {
        // == 너비우선탐색과 플래그를 사용하는 방법 => 플래그를 계속 다음 레벨로 넘겨줌 ==

        // [시나리오]
        // 1 flag (flag 만나면 다음으로 넘김)
        // 2 3 4 flag (flag 만나면 다음으로 넘김)
        // 5 6 7 8 flag (flag 만나면 다음으로 넘김)

        List<Integer> nodes = new LinkedList<>();
        Queue<Node> queue = new LinkedList<>();
        int nowLevel = 1;
        queue.add(root);
        queue.add(null); // 플래그삽입

        while(queue.size() != 0) {
            Node node = queue.remove();
            if( node != null ) {
                // == flag 아니라면 ==
                if(nowLevel == level) {
                    nodes.add(node.data);
                }
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            } else {
                // == flag 라면 ==
                if(queue.size() != 0) {
                    queue.add(null);
                    nowLevel++;
                    if(nowLevel > level) break;
                }
            }
        }
        return nodes;
    }

    /* createLevelLinkedList - 전체를 리스트로 반환하기 */
    public static ArrayList<LinkedList<Node>> createLevelLinkedList( Node root ) {
        ArrayList<LinkedList<Node>> result = new ArrayList<>();

        // == 루트방문 ==
        LinkedList<Node> current = new LinkedList();
        if(root != null) current.add(root);

        while(current.size() > 0) {
            result.add(current); // 이전리스트저장
            LinkedList<Node> parents = current; // 이전리스트가부모
            current = new LinkedList();
            for(Node parent : parents) {
                if(parent.left != null) current.add(parent.left);
                if(parent.right != null) current.add(parent.right);
            }
        }
        return result;
    }

}