[Java] 거꾸로 BFS

1. 문제

이진 트리 자료구조를 순회하는 새로운 알고리즘을 설계하였고, 그것을 '거꾸로 BFS'라고 지었다.

기존의 BFS는 가장 상위 노드인 루트 노드부터, 깊이 순서대로 노트를 순회하는 방법이다. 또한 순회의 순서는 왼쪽부터 오른쪽으로 이루어졌다.

 

'거꾸로 BFS' 순회 방법은 가장 하위 노드인 리프 노드부터 시작한다. 각 리프 노드를 오른쪽부터 왼쪽 순으로 순회한다.

 

그 다음에는 이미 순회한 리프 노드를 제거하고, 나머지 부분 트리에서 리프 노드를 오른쪽부터 왼쪽 순으로 순회한다.

 

위 과정을 모든 노드를 순회할 때까지 반복한다.

 

전체 노드의 수가 N 으로 주어지며,  부모-자식 관계가 left[i] = { 부모노드의 인덱스, 왼쪽 자식노드의 인덱스} , right[i] = {부모 노드의 인덱스, 오른쪽 자식노드의 인덱스} 로 주어질 때, 

위에서 묘사된 '거꾸로 BFS'를 구현하시오.

 

 

 

2. 입력 설명

• 0 < N <= 100

 

 

 

3. 출력 설명

순회하는 노드의 인덱스의 순서로 이루어진 배열

 

 

4. 매개변수 형식

• N = 6
• left = {{0,1}, {1,5}, {2,3}}
• right = {{0,2}, {3,4}}

 

 

 

5. 반환값 형식

{4, 5, 3, 1, 2, 0}

 

 

 

6. 입출력 예시 설명

 

 

 

 

7. 코드 구현

import java.util.*;

class Solution {

    boolean[] isVisited;
    int[][] adjList;
    List<Integer> result;

    public int[] solution(int N, int[][] left, int[][] right) {
        adjList = new int[N][];

        // left자식, right자식 초기화
        for (int i = 0; i < N; i++) {
            adjList[i] = new int[]{-1, -1};
        }

        // left 자식 추가
        for (int[] ints : left) {
            int parent = ints[0];
            int child = ints[1];

            adjList[parent][0] = child;
        }

        // right 자식 추가
        for (int[] inits : right) {
            int parent = inits[0];
            int child = inits[1];

            adjList[parent][1] = child;
        }

        isVisited = new boolean[N];
        Arrays.fill(isVisited, false);
        result = new ArrayList<>();
        
        // 루트 노드에 도달하게 되면 종료
        while(!isVisited[0]) {
        	dfs(0);
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
    
    
    void dfs(int node) {
    	int left = adjList[node][0];
        int right = adjList[node][1];
        
        // 자식이 없거나, 자식이 이미 들렀다면 이 노드가 리프 노드
        if ((left == -1 || isVisited[left])
                && (right == -1 || isVisited[right])) {
            result.add(node);
            isVisited[node] = true;
            return;
        }
        
        // 자식이 있고, 들리지 않았으면 더 밑으로 내려가야 한다.
        // 우측 자식을 먼저 들러야 우측부터 좌측으로 읽는다.
        if (right >= 0 && !isVisited[node]) {
            dfs(right);
        }
        if (left >= 0 && !isVisited[left]) {
            dfs(left);
        }
    }
}