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

문제

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

풀이

• 전위 순회, 중위 순회, 후위 순회 결과 출력

전위, 중위, 후위 순회를 처음 보신 분은 여기로 가셔서 간단하게 확인하고 오시는 걸 추천드립니다.

각각의 결과를 리턴할 메서드를 구현해줍니다.

	// 전위 순회
	public static String preorder(String node) {
		// 자식 노드가 없을 경우 출력할 수 없으니, 공백으로 리턴
		if (node.equals(".")) {
			return "";
		}
		
		// 왼쪽 자식 노드, 오른쪽 자식 노드
		String left = tree.get(node)[0];
		String right = tree.get(node)[1];
		
		// (루트) (왼쪽 자식) (오른쪽 자식)
		return node + preorder(left) + preorder(right);
	}

• 왼쪽 자식 노드, 오른쪽 자식 노드를 추출하여 재귀

	// 중위 순회
	public static String inorder(String node) {
		if (node.equals(".")) {
			return "";
		}
		
		String left = tree.get(node)[0];
		String right = tree.get(node)[1];
		
		// (왼쪽 자식) (루트) (오른쪽 자식)
		return inorder(left) + node + inorder(right);
	}

	// 후위 순회
	public static String postorder(String node) {
		if (node.equals(".")) {
			return "";
		}
		
		String left = tree.get(node)[0];
		String right = tree.get(node)[1];
		
		// (왼쪽 자식) (오른쪽 자식) (루트)
		return postorder(left) + postorder(right) + node;
	}

코드

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

public class Main_1991 {
	static int n;
	static Map<String, String[]> tree = new HashMap<>();
	
	// 전위 순회
	public static String preorder(String node) {
		// 자식 노드가 없을 경우 출력할 수 없으니, 공백으로 리턴
		if (node.equals(".")) {
			return "";
		}
		
		// 왼쪽 자식 노드, 오른쪽 자식 노드
		String left = tree.get(node)[0];
		String right = tree.get(node)[1];
		
		// (루트) (왼쪽 자식) (오른쪽 자식)
		return node + preorder(left) + preorder(right);
	}
	
	// 중위 순회
	public static String inorder(String node) {
		if (node.equals(".")) {
			return "";
		}
		
		String left = tree.get(node)[0];
		String right = tree.get(node)[1];
		
		// (왼쪽 자식) (루트) (오른쪽 자식)
		return inorder(left) + node + inorder(right);
	}

	// 후위 순회
	public static String postorder(String node) {
		if (node.equals(".")) {
			return "";
		}
		
		String left = tree.get(node)[0];
		String right = tree.get(node)[1];
		
		// (왼쪽 자식) (오른쪽 자식) (루트)
		return postorder(left) + postorder(right) + node;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String root = st.nextToken();
			String left = st.nextToken();
			String right = st.nextToken();
			tree.put(root, new String[] {left, right});
		}
		
		// 루트 노드인 A부터 시작
		System.out.println(preorder("A"));
		System.out.println(inorder("A"));
		System.out.println(postorder("A"));
	}

}