[java]트리 순회 - 백준1991

문제



풀이

문제 해석을 하자면,

  • 전위, 중위, 후위순회를 구하는 문제이며 트리 순회의 기본이 되는 개념이므로 모른다면 구글링을 해서 익혀두자.


풀이

  • 문자보단 숫자가 좋아서, 숫자로 바꿔서 노드를 입력받았다.
    • 이때, 숫자로 바꿔서 노드를 기록하다보니 “.” 은 -18로 기록됨을 기억해두자.
    • 또한, 루트 노드 무조건 A이고, 이진트리라서 간단히 2차원 배열로 입력받았다.



코드

/**
 * 전위, 중위, 후위순회
 * 숫자로 바꿔서 노드 기록하다보니 "." 은 -18로 기록
 * 참고 : 루트 노드 무조건 A, 이진트리라서 간단히 2차원 배열로 해결하였음
 */

static int[][] inArr = new int[30][2]; // left, right 기록 => 이진트리니까 그냥 배열로

static void preTravel(StringBuilder sb, int root) {
    if(root == -1 || root == -18) return;
    char temp = (char) (root+'A'-1);
    sb.append(temp); // root
    preTravel(sb, inArr[root][0]); // left
    preTravel(sb, inArr[root][1]); // right
}
static void inTravel(StringBuilder sb, int root) {
    if(root == -1 || root == -18) return;
    char temp = (char) (root+'A'-1);
    inTravel(sb, inArr[root][0]); // left
    sb.append(temp); // root
    inTravel(sb, inArr[root][1]); // right
}
static void postTravel(StringBuilder sb, int root) {
    if(root == -1 || root == -18) return;
    char temp = (char) (root+'A'-1);
    postTravel(sb, inArr[root][0]); // left
    postTravel(sb, inArr[root][1]); // right
    sb.append(temp); // root
}

public static void main(String[] args) throws IOException {
    // input
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer stk;
    int N = Integer.parseInt(br.readLine());
    for(int i = 0 ; i<2; i++)
        Arrays.fill(inArr[i], -1);
    for(int i = 0 ; i<N;i++) {
        stk = new StringTokenizer(br.readLine(), " ");
        int a = stk.nextToken().charAt(0)-'A' +1; // index 1번부터 사용
        int b = stk.nextToken().charAt(0)-'A' +1;
        int c = stk.nextToken().charAt(0)-'A' +1;
        inArr[a][0] = b; inArr[a][1] = c;
    }
    // run
    StringBuilder sb = new StringBuilder();
    preTravel(sb, 1); sb.append('\n');
    inTravel(sb, 1); sb.append('\n');
    postTravel(sb, 1); sb.append('\n');
    // output
    System.out.println(sb);
}



느낀점

생략

댓글남기기

참고