[Java] 백준 - 1991번 : 트리 순회

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

1991번: 트리 순회

 

 

 

 

 

import java.io.*;
import java.util.*;
public class Main {
	//완벽한 이진트리가 아니기 때문에 arraylist로는 복잡해질 것 같아서 해시맵을 활용하여 부모노드를 키로, 자식노드를 값으로 설정
	static HashMap<String, Node> tree;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		//줄 수
		int n = Integer.parseInt(br.readLine());
		//tree 초기화
		tree = new HashMap<>();
		
		//for문으로 노드 입력 받기
		for (int i = 0; i < n; i++) {
			String[] s = br.readLine().split(" ");
			//첫 글자는 부모노드, 그 다음은 왼쪽 노드, 오른쪽 노드로 구분되어 그대로 추가
			tree.put(s[0], new Node(s[1], s[2]));
		}

		//전위순회 함수 호출
		System.out.println(preOrder("A"));
		//중위순회 함수 호출
		System.out.println(inOrder("A"));
		//후위순회 함수 호출
		System.out.println(postOrder("A"));
	}
	
	//전위순회
	public static String preOrder(String word) {
		StringBuilder sb = new StringBuilder(word);
		Node node = tree.get(word);

		if (!node.left.equals(".")) sb.append(preOrder(node.left));
		if (!node.right.equals(".")) sb.append(preOrder(node.right));
		
		return sb.toString();
	}
	
	//중위순회
	public static String inOrder(String word) {
		StringBuilder sb = new StringBuilder();
		Node node = tree.get(word);

		if (!node.left.equals(".")) sb.append(inOrder(node.left));
		sb.append(word);
		if (!node.right.equals(".")) sb.append(inOrder(node.right));
		
		return sb.toString();
	}
	
	//후위순회
	public static String postOrder(String word) {
		StringBuilder sb = new StringBuilder();
		Node node = tree.get(word);

		if (!node.left.equals(".")) sb.append(postOrder(node.left));
		if (!node.right.equals(".")) sb.append(postOrder(node.right));
		sb.append(word);
		
		return sb.toString();
	}
}

class Node {
	String left, right;
	public Node(String l, String r) {
		this.left = l;
		this.right = r;
	}
}

 

문제	결과	메모리	시간	코드 길이
1991	맞았습니다!!	14176 KB	128 ms	1519 B