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

풀이 ① - 인접 리스트 + 재귀 함수

인접 리스트 List<Character>[] lists에 트리 저장, 재귀 함수로 트리 순회 구현

1. 아이디어

1) 트리의 노드 연결 정보를 인접 리스트 List<Character>[] lists에 저장

• 각 노드의 Left Child, Right Child 저장
  ex) lists[0]: 루트 노드 'A'의 Left Child, Right Child 저장
  
  

2) 재귀 함수로 각 트리 순회 구현

• 전위 순회 (Preorder): Parent → Left Child → Right Child
• 중위 순회 (Inorder): Left Child → Parent → Right Child
• 후위 순회 (Postorder): Left Child → Right Child → Parent
  
  

char[] tree에 전체 트리(노드들)를 저장하지 않고,
인접 리스트 List<Character>[]를 사용한 이유

• 입력 트리의 형태가 "완전 이진 트리"가 아닌, 그냥 이진 트리
  
  
• 트리가 최악으로 Unbalance 할 수 있음
  • ex) 최악의 경우로 트리가 오른쪽으로만 길게 뻗친 형태 (Right Child 만 존재)인 경우,
    char[] tree의 index => 루트 [1], [3], [7], [15], ..., [2^26 - 1]
  • n 최대 노드 개수: 26
  • 부모 노드가 [i]이면, Left Child 는 [i * 2], Right Child 는 [i * 2 + 1])
    
    
• 메모리 초과 발생
  => 최대 char[] tree 의 메모리: (2^26 - 1) x 2 byte = 134,217,726 byte ~= 대략 134 MB >> 128 MB

2. 자료구조

• List<Character>[], ArrayList<Character>[]: 각 노드의 Left Child, Right Child 저장

3. 시간 복잡도

• 1개 부모 노드에서 재귀 호출 2번 수행

  • 대충 전체 n개 노드에서, 재귀 호출 2번 모두 수행 가정
  • 트리 순회 1번 당, O(2 x n)

• 트리 순회 총 3번이므로, 총 시간 복잡도: O(6 x n)
  => n 최대값 대입: 6 x 26 = 156

코드

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

public class Main {
	static int n;				// 이진 트리의 노드 개수
	static List<Character>[] lists;		// 각 노드의 left, right child 저장
	static StringBuilder sb = new StringBuilder();		// 출력 값

	static void preorder(char parent) {
		List<Character> list = lists[parent - 'A'];
		char leftChild = list.get(0);
		char rightChild = list.get(1);

		// Parent -> Left Child -> Right Child
		sb.append(parent);
		if (leftChild != '.')
			preorder(leftChild);
		if (rightChild != '.')
			preorder(rightChild);
	}

	static void inorder(char parent) {
		List<Character> list = lists[parent - 'A'];
		char leftChild = list.get(0);
		char rightChild = list.get(1);

		// Left Child -> Parent -> Right Child
		if (leftChild != '.')
			inorder(leftChild);
		sb.append(parent);
		if (rightChild != '.')
			inorder(rightChild);
	}

	static void postorder(char parent) {
		List<Character> list = lists[parent - 'A'];
		char leftChild = list.get(0);
		char rightChild = list.get(1);

		// Left Child -> Right Child -> Parent
		if (leftChild != '.')
			postorder(leftChild);
		if (rightChild != '.')
			postorder(rightChild);
		sb.append(parent);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		lists = new ArrayList[n];		// [0 ~ n-1]
		for (int i = 0; i < n; i++)
			lists[i] = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			char parent = st.nextToken().charAt(0);
			char leftChild = st.nextToken().charAt(0);
			char rightChild = st.nextToken().charAt(0);

			lists[parent - 'A'].add(leftChild);
			lists[parent - 'A'].add(rightChild);
		}

		// 루트 노드 'A' 에서 시작
		preorder('A');
		sb.append("\n");

		inorder('A');
		sb.append("\n");

		postorder('A');
		sb.append("\n");

		System.out.println(sb);
	}
}

풀이 ② - Tree 직접 구현 + 재귀 함수

Tree를 직접 구현하여 트리 저장, 재귀 함수로 트리 순회 구현

1. 아이디어

Tree를 직접 구현

1) 트리 노드 추가

• Left Child 추가
• Right Child 추가

2) 재귀 함수로 각 트리 순회 구현

• 전위 순회 (Preorder): Parent → Left Child → Right Child
• 중위 순회 (Inorder): Left Child → Parent → Right Child
• 후위 순회 (Postorder): Left Child → Right Child → Parent

입력 트리가 이진 트리 형태이고,
입력 노드 연결 정보가 Parent - Left Child - Right Child 의 순서로 주어지므로,
Tree 직접 구현해서 풀이 가능

2. 자료구조

• Tree: Node들을 갖는 트리 구현 클래스

3. 시간 복잡도

• 1개 부모 노드에서 재귀 호출 2번 수행

  • 대충 전체 n개 노드에서, 재귀 호출 2번 모두 수행 가정
  • 트리 순회 1번 당, O(2 x n)

• 트리 순회 총 3번이므로, 총 시간 복잡도: O(6 x n)
  => n 최대값 대입: 6 x 26 = 156

코드

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

class Node {
	public char data;
	public Node leftChild;
	public Node rightChild;

	public Node(char data) {
		this.data = data;
	}
}

class Tree {
	public Node root;
	public int size;

	public Tree(Node root) {
		this.root = root;
		size++;
	}

	/* 트리에서 parentData 값을 갖는 parent 노드를 찾아서,
	   leftData 값을 갖는 leftChild 노드 추가 */
	public void addLeft(char parentData, char leftData) {
		if (root == null) {
			root = new Node(parentData);		// Root 추가
			root.leftChild = new Node(leftData);	// Left Child 추가
			size += 2;
		}
		else
			addLeft(root, parentData, leftData);
	}

	public void addLeft(Node node, char parentData, char leftData) {
		if (node == null)			// 못 찾은 경우
			return;
		else if (node.data == parentData) {	// 찾은 경우
			node.leftChild = new Node(leftData);
			size++;
		}
		else {
			addLeft(node.leftChild, parentData, leftData);
			addLeft(node.rightChild, parentData, leftData);
		}
	}

	/* 트리에서 parentData 값을 갖는 parent 노드를 찾아서,
	   rightData 값을 갖는 rightChild 노드 추가 */
	public void addRight(char parentData, char rightData) {
		if (root == null) {
			root = new Node(parentData);		// Root 추가
			root.rightChild = new Node(rightData);	// Right Child 추가
			size += 2;
		}
		else
			addRight(root, parentData, rightData);
	}

	public void addRight(Node node, char parentData, char rightData) {
		if (node == null)			// 못 찾은 경우
			return;
		else if (node.data == parentData) {	// 찾은 경우
			node.rightChild = new Node(rightData);
			size++;
		}
		else {
			addRight(node.leftChild, parentData, rightData);
			addRight(node.rightChild, parentData, rightData);
		}
	}

	public StringBuilder sb;

	/* 전위 순회: Parent -> Left Child -> Right Child */
	public void preorder(Node parent) {
		sb.append(parent.data);
		if (parent.leftChild != null)
			preorder(parent.leftChild);
		if (parent.rightChild != null)
			preorder(parent.rightChild);
	}

	/* 중위 순회: Left Child -> Parent -> Right Child */
	public void inorder(Node parent) {
		if (parent.leftChild != null)
			inorder(parent.leftChild);
		sb.append(parent.data);
		if (parent.rightChild != null)
			inorder(parent.rightChild);
	}

	/* 후위 순회: Left Child -> Right Child -> Parent */
	public void postorder(Node parent) {
		if (parent.leftChild != null)
			postorder(parent.leftChild);
		if (parent.rightChild != null)
			postorder(parent.rightChild);
		sb.append(parent.data);
	}
}

public class Main_Tree_Dev {
	static int n;		// 이진 트리의 노드 개수
	static Tree tree;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		tree = new Tree(new Node('A'));
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			char parentData = st.nextToken().charAt(0);
			char leftData = st.nextToken().charAt(0);
			char rightData = st.nextToken().charAt(0);

			if (leftData != '.')
				tree.addLeft(parentData, leftData);
			if (rightData != '.')
				tree.addRight(parentData, rightData);
		}

		tree.sb = new StringBuilder();
		tree.preorder(tree.root);
		tree.sb.append("\n");

		tree.inorder(tree.root);
		tree.sb.append("\n");

		tree.postorder(tree.root);
		tree.sb.append("\n");
		System.out.println(tree.sb);
	}
}