트리 dfs 탐색

0을 root로 둔 트리에서
leaf 노드를 출력 해보기

n개의 노드를 담은 배열 n, 각 노드간 연결정보를 가지고 있는 배열 edges를 제공

1. 각 노드별 간선정보를 저장한 배열 link 만들기
2. 탐색 시작 (stack 구현)
3. 방문한 노드와 연결된 노드를 방문하지 않았으면 push
4. 현재 노드와 연결된 노드가 1개일 경우 Leaf Node

 

 

    public void solution(int[] n, int[][] edges){
        boolean[] ck = new boolean[n.length];
        List[] link = new List[n.length];
        Stack<Integer> st = new Stack<Integer>();
        int cur =0;
        int next = 0;

        for(int i=0; i<link.length; i++){
            link[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<edges.length; i++){
            link[edges[i][0]].add(edges[i][1]);
            link[edges[i][1]].add(edges[i][0]);
        }
        //1. 0부터 시작
        st.add(0);
        while(!st.isEmpty()){
            cur = st.pop();
            //System.out.println(cur+" 방문");
            ck[cur] = true; //방문처리
            //연결지점 탐색
            for(int i=0; i<link[cur].size(); i++){
                next = (int) link[cur].get(i);
                if(ck[next]){
                    if(link[cur].size() == 1){
                        System.out.println(cur+" is leafNode");
                    }
                    continue;
                }else{
                    st.push(next);
                }
            }
        }

/*
        for(int i=0; i<link.length; i++){
            System.out.println(link[i]);
        }
*/
    }

    public static void main(String[] args) {
        test06 tc = new test06();

        int[] n = {0,1,2,3,4,5};
        int[][] edges = {{0,1},{2,0},{4,5},{1,3},{1,4}};

        tc.solution(n,edges);

    }