백준 1991번: 트리 순회 with Java

트리 순회 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

70854

46253

35564

67.173%

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 입력 1 복사

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력 1 복사

ABDCEFG
DBAECFG
DBEGFCA

 

 

 

---

 

문제는 간단하다.

트리 입력 받고

이걸 전위-중위-후위 순회 시킨 결과를 출력!

ㅎㅎ

 

잠깐!! 여기서 은근 헷갈리는 전위 - 중위 - 후위 순회를 정리해보도록 하자.

 

* 전위순회(Preorder): Root - L - R 부모 노드 방문 후 왼쪽 자식 -> 왼쪽으로 겁내 내려간다. 

* 중위순회(Inorder): L - Root -R 왼쪽 자식 - 부모 - 오른쪽 자식 

* 후위순회(Postorder): L - R - Root 왼쪽 자식 - 오른쪽 자식 - 부모노드 (패륜..)

 

갠적으로 외울 때 삼각형을 그리면서 외웠던 기억이 난다.

 

와 발그림 ㅈㅅ요

여기서 전위순회하면 1245367 중위순회하면 4251637 후위순회하면 4526731 될...거다 (맞겠지?)

 

은근 영어로 문제가 나올 때가 있어서 잘 외워둬야 함 

 

자 그러면 이걸 출력하면 된다는 거...! 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        Map<String, TreeNode> tree = new HashMap<>();
        
        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            String parent = input[0];
            String left = input[1];
            String right = input[2];
            
            // 노드 생성, getOrDefault 사용. 부모 있으면 parent 노드 데려오고 없으면 새로 생성 
            TreeNode node = tree.getOrDefault(parent, new TreeNode(parent));
            
            // 왼쪽 오른쪽 노드.. .이면 없으니까 null로 넣어줌
            node.left = left.equals(".") ? null : new TreeNode(left);    
            node.right = right.equals(".") ? null : new TreeNode(right);
            
            // 왼쪽 자식이 존재하면 트리에 추가
            if (node.left != null) tree.put(left, node.left);
            
            // 오른쪽 자식이 존재하면 트리에 추가
            if (node.right != null) tree.put(right, node.right);
            
            // 부모 노드를 트리에 추가
            tree.put(parent, node);
        }

        // 순회 결과를 담을 StringBuilder 생성
        StringBuilder preorder = new StringBuilder();
        StringBuilder inorder = new StringBuilder();
        StringBuilder postorder = new StringBuilder();

        // 루트 노드 'A'에서 시작해서 순회 시작
        traversePreorder(tree.get("A"), preorder);
        traverseInorder(tree.get("A"), inorder);
        traversePostorder(tree.get("A"), postorder);

        // 결과 출력
        System.out.println(preorder.toString());
        System.out.println(inorder.toString());
        System.out.println(postorder.toString());
    }

    // 전위 순회 (루트 → 왼쪽 → 오른쪽)
    static void traversePreorder(TreeNode node, StringBuilder sb) {
        // 현재 노드가 null이면 종료
        if (node == null) return;

        // 루트 노드 값 추가
        sb.append(node.value);
        
        // 왼쪽 자식으로 재귀 호출
        traversePreorder(node.left, sb);
        
        // 오른쪽 자식으로 재귀 호출
        traversePreorder(node.right, sb);
    }

    // 중위 순회 (왼쪽 → 루트 → 오른쪽)
    static void traverseInorder(TreeNode node, StringBuilder sb) {
        // 현재 노드가 null이면 종료
        if (node == null) return;

        // 왼쪽 자식으로 재귀 호출
        traverseInorder(node.left, sb);
        
        // 루트 노드 값 추가
        sb.append(node.value);
        
        // 오른쪽 자식으로 재귀 호출
        traverseInorder(node.right, sb);
    }

    // 후위 순회 (왼쪽 → 오른쪽 → 루트)
    static void traversePostorder(TreeNode node, StringBuilder sb) {
        // 현재 노드가 null이면 종료
        if (node == null) return;

        // 왼쪽 자식으로 재귀 호출
        traversePostorder(node.left, sb);
        
        // 오른쪽 자식으로 재귀 호출
        traversePostorder(node.right, sb);
        
        // 루트 노드 값 추가
        sb.append(node.value);
    }

    // 트리 노드 클래스
    static class TreeNode {
        String value;  // 노드 값
        TreeNode left, right;    // 왼쪽 자식, 오른쪽 자식

        TreeNode(String value) {
            this.value = value;
            this.left = this.right = null;
        }
    }
}

 

 

 

 

지피티의 도움을 받았다...

getOrDefalut... 처음 써봄.......

코드가 은근 간단한데 어렵다. 재귀에 익숙해질 때도 되지 않았나 싶은데..