고민의 흔적

70번 트리 순회

내가 떠올린 풀이 해설

2차원 배열에 트리 데이터를 저장한다. 저장할 때 index화 하여 저장한다. 전위 순회 함수를 구현해 실행한다. 중위 순회, 후위 순회도 같은 과정으로 구현한다.

전위 순회 순서

현재 노드 -> 왼쪽 노드 -> 오른쪽 노드

중위 순회 순서

왼쪽 노드 -> 현재 노드 -> 오른쪽 노드

후위 순회 순서

왼쪽 노드 -> 오른쪽 노드 -> 현재 노드

정확한 풀이

import java.io.*;
import java.util.*;
public class Baek1991 {
	static int[][] tree;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		tree = new int[26][2];
		for(int i = 0; i < n; i++) {
			String[] str = br.readLine().split(" ");
			int node = str[0].charAt(0) - 'A';
			char left = str[1].charAt(0);
			char right = str[2].charAt(0);
			
			if(left == '.') {
				tree[node][0] = -1; 
			}
			else {
				tree[node][0] = left - 'A';
			}
			if(right == '.') {
				tree[node][1] = -1;
			}
			else {
				tree[node][1] = right - 'A';
			}
		}
		preOrder(0);
		System.out.println();
		inOrder(0);
		System.out.println();
		postOrder(0);
		System.out.println();
	}
	private static void postOrder(int now) {
		if(now == -1) {
			return;
		}
		postOrder(tree[now][0]);
		postOrder(tree[now][1]);
		System.out.print((char)(now + 'A'));
	}
	private static void inOrder(int now) {
		if(now == -1) {
			return;
		}
		inOrder(tree[now][0]);
		System.out.print((char)(now + 'A'));
		inOrder(tree[now][1]);
	}
	private static void preOrder(int now) {
		if(now == -1) {
			return;
		}
		System.out.print((char)(now + 'A'));
		preOrder(tree[now][0]);
		preOrder(tree[now][1]);
	}
}

오늘의 회고

오늘은 이진 트리 한 문제를 풀었습니다. 주어진 자료구조 형태만 충실히 구현하면 되는 문제라고 나와있었는데 많이 헤맸습니다. 이제 앞으로 배워야 할 알고리즘이 세그먼트 트리, 최소 공통 조상, 조합, 동적 계획법(DP) 4개가 남았는데 이 책을 끝내면 이제 단원별이 아닌 무작위로 문제를 뽑아서 풀 생각입니다. 그동안 배웠던 알고리즘으로 응용을 해서 풀어야 되는데 걱정이 되네요 꾸준히 하다 보면 목표에 도달할 것이라고 생각합니다. 꾸준히 열심히 하겠습니다.