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

📝 문제

백준 - 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;
	}
}

---

📌 결과

---

📌 Point

전위, 중위, 후위순회 함수에서 중요한 것은 매개변수인 word를 언제 stringbuilder에 추가하는가 이다.

전위순회는 처음 함수를 방문할 때, 중위순회는 왼쪽을 방문한 후에, 후위순회는 왼쪽, 오른쪽 방문 후에 추가함