[백준/JAVA] 1991번: 트리 순회

🔺 문제

1991번: 트리 순회

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][] tree;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        
        tree = new int[26][2];
        for(int i = 0 ; i < n ; i++) {
            String[] tmp = br.readLine().split(" ");
            int  node  = tmp[0].charAt(0) - 'A';
            char left  = tmp[1].charAt(0);
            char right = tmp[2].charAt(0);
            
            if(left == '.') tree[node][0] = -1;
            else            tree[node][0] = left - 'A';
            
            if(right == '.') tree[node][1] = -1;
            else             tree[node][1] = right - 'A';
        }
        
        preOrder(0);
        System.out.println();
        
        inOrder(0);
        System.out.println();
        
        postOrder(0);
        System.out.println();
    }
    
    // 전위 순회
    public static void preOrder(int now) {
        if(now == -1) return;
        System.out.print((char) (now + 'A'));   // 1. 현재 노드
        preOrder(tree[now][0]);                 // 2. 왼쪽 탐색
        preOrder(tree[now][1]);                 // 3. 오른쪽 탐색
    }
    // 중위 순회
    public static void inOrder(int now) {
        if(now == -1) return;
        inOrder(tree[now][0]);                  // 1. 왼쪽 탐색
        System.out.print((char) (now + 'A'));   // 2. 현재 노드
        inOrder(tree[now][1]);                  // 3. 오른쪽 탐색
    }
    // 후위 순회
    public static void postOrder(int now) {
        if(now == -1) return;
        postOrder(tree[now][0]);                // 1. 왼쪽 탐색
        postOrder(tree[now][1]);                // 2. 오른쪽 탐색
        System.out.print((char) (now + 'A'));   // 3. 현재 노드
    }
}

✅ 해결 아이디어
✔ 전위 순회 : 루트 →  L → R / 중위 순회 :  L → 루트 → R / 후위 순회 : L → R → 루트 
- 2차원 배열 사용했으나, 클래스로 노드 구현해도 괜찮음

 

 

---

🔺 다른 풀이들

- 클래스로 노드를 구현해 푸셨다 (Node 클래스 변수 - char value, Node left, Node right)

[Java] 백준 / 트리 순회 / 1991번

 

 

- 과정 설명이 굿 (복습용)

백준 1991 트리 순회 Java

 

 

- 이해하기 좋은 풀이... (Node 클래스 변수 - char left, char right)

로그인

 

 

- dfs 활용하심 ... 신기방기

로그인

---

💬 느낀 점

다음엔 잘 풀 수 있을 것 같다!

 

 

1회독	2회독	3회독	4회독	5회독
V	6/29

 

 

(+6/29 2회독)

음.. 쉽지 않구만.. 위 코드랑 거의 차이 없는데 삼항 연산자 써줬음

import java.util.*;
import java.io.*;
 
public class Main {
    static int[][] tree;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        tree = new int[26][2];
 
        while(N-->0) {
            String[] tmp = br.readLine().split(" ");
            int  node  = tmp[0].charAt(0) - 'A';
            char left  = tmp[1].charAt(0);
            char right = tmp[2].charAt(0);
            
            tree[node][0] = (left == '.') ? -1 : (left - 'A');
            tree[node][1] = (right == '.') ? -1 : (right - 'A');
        }
        
        preOrder(0);
        System.out.println();
        
        inOrder(0);
        System.out.println();
        
       postOrder(0);
        System.out.println();
    }
    
    // 전위 순회
    private static void preOrder(int now) {
        if(now == -1)   return;
        System.out.print((char) (now + 'A'));   // 1. 현재 노드
        preOrder(tree[now][0]);                 // 2. 왼쪽 탐색
        preOrder(tree[now][1]);                 // 3. 오른쪽 탐색
        
    }
    
    // 중위 순회
    private static void inOrder(int now) {
        if(now == -1)   return;
        inOrder(tree[now][0]);                  // 1. 왼쪽 탐색
        System.out.print((char) (now + 'A'));   // 2. 현재 노드
        inOrder(tree[now][1]);                  // 3. 오른쪽 탐색
    }
 
    // 후위 순회
    private static void postOrder(int now) {
        if(now == -1)   return;
        postOrder(tree[now][0]);                // 1. 왼쪽 탐색
        postOrder(tree[now][1]);                // 2. 오른쪽 탐색
        System.out.print((char) (now + 'A'));   // 3. 현재 노드
    }    
}