[SW expert Academy] SWEA 1231번 중위순회 자바(Java)

[D4] [S/W 문제해결 기본] 9일차 - 중위순회 - 1231

문제 링크

성능 요약

메모리: 19,112 KB, 시간: 125 ms, 코드길이: 1,065 Bytes

제출 일자

2024-01-04 00:54

 

접근 방법

1. 완전 이진 트리임으로 배열로 할 수 있다.

2. 이진 트리에서는 왼쪽 자식 노드는 현재 인덱스 * 2, 오른쪽 자식은 현재 인덱스 * 2 + 1이다.

3. 인덱스를 구한후 N보다 작다면 호출 한다. ( 중위 순회는 LVR(왼쪽가운데오른쪽 순서로 진행)

4. 순서대로만 구현하면 아주 쉬운 문제

 

풀이 코드

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Solution {
    static String[] graph;
    static StringBuilder sb = new StringBuilder();
    static int n;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int tc = 1; tc <= 10; tc++) {
            n = Integer.parseInt(br.readLine());
            graph = new String[n+1];
            for(int i = 1; i <= n; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                graph[Integer.parseInt(st.nextToken())] = st.nextToken();
            }
            sb.append("#" + tc + " ");
            // 중위순회
            LVR(1);
            sb.append("\n");
        }
        System.out.println(sb);
    }
    // V는 현재 노드를 뜻함
    private static void LVR(int V){
        // 왼쪽 먼저 구해준다.
        int left = V * 2;
        // 범위내에 있다면 왼쪽 호출
        if(left <= n){
            LVR(left);
        }
        // 가운데 노드의 key값을 저장한다.
        sb.append(graph[V]);
        // 오른쪽 인덱스를 구한뒤 범위내라면 호출한다.
        if(left + 1 <= n){
            LVR(left+1);
        }
    }
}

 

출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do