백준 1991번 ) 트리 순회 (java)

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

문제

 

 

풀이

import java.io.*;
import java.util.*;

public class Main {

    static class Node{
        int left;
        int right;

        public Node(int left, int right){
            this.left = left;
            this.right = right;
        }
    }
    static List<Node>[] list;
    static int none = '.' - 'A';
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));      
        int n = Integer.parseInt(br.readLine());

        list = new ArrayList[n+1];
        for(int i=0; i<n; i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0; i<n; i++){
            String line = br.readLine();
            StringTokenizer st = new StringTokenizer(line," ");
            int data = st.nextToken().charAt(0) - 'A';
            int left = st.nextToken().charAt(0) - 'A';
            int right = st.nextToken().charAt(0) - 'A';
            list[data].add(new Node(left, right));
        }

        preorder(0);
        System.out.println();
        inorder(0);
        System.out.println();
        postorder(0);
    }

    static void preorder(int start){
        for(Node node : list[start]) {
            int l = node.left;
            int r = node.right;

            System.out.print((char)(start+'A'));
            if( l != none) preorder(l);
            if( r != none) preorder(r);
        }
    }

    static void inorder(int start){
        for(Node node : list[start]){
            int l = node.left;
            int r = node.right;

            if(l!= none) inorder(l);
            System.out.print((char)(start+'A'));
            if(r!= none) inorder(r);
        }
    }

    static void postorder(int start){
        for(Node node : list[start]){
            int l = node.left;
            int r = node.right;

            if(l!= none) postorder(l);
            if(r!= none) postorder(r);
            System.out.print((char)(start+'A'));
        }
    }
}

 

트리를 List<Node>[] list = new ArrayList[n];  형식으로 구현하였다.

에지를 하나씩 따라가지 않고 연결리스트로 트리 구조 구현.

 

저장할때는 List[data] 로 찾을 수 있도록 정수형태로 변환해주었다. 따라서 캐릭터를 정수형으로 변환하였다.

순회 방법은 정석대로 풀이.

 

 

꼭 트리 형태 구현하는 것 기억해두기!!