[알고리즘] 중위 순회
2024. 2. 12. 17:16ㆍ알고리즘 풀이/Java
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static class Node {
int position;
String value;
Node left;
Node right;
public Node(int position, String value, Node left, Node right) {
this.position = position;
this.value = value;
this.left = left;
this.right = right;
}
}
static class Tree {
Node root;
public Tree(int position, String value) {
root = getNewNode(position, value);
}
public Node getNewNode(int position, String value) {
return new Node(position, value, null, null);
}
public void makeLeftChild(int position, int childPosition, String value) {
Node childNode = getNewNode(childPosition, value);
Node parentNode = searchNode(root, position);
parentNode.left = childNode;
}
public void makeRightChild(int position, int childPosition, String value) {
Node childNode = getNewNode(childPosition, value);
Node parentNode = searchNode(root, position);
parentNode.right = childNode;
}
public Node getRoot() {
return root;
}
public void inorder(Node curNode) {
if (curNode.value == null) {
return;
}
inorder(curNode.left);
sb.append(curNode.value);
inorder(curNode.right);
}
public Node searchNode(Node curNode, int position) {
if (curNode == null) {
return null;
}
if (curNode.position == position) {
return curNode;
}
Node leftNode = searchNode(curNode.left, position);
Node rightNode = searchNode(curNode.right, position);
if (leftNode != null) {
return leftNode;
} else {
return rightNode;
}
}
}
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int testCase = 1; testCase <= 10; testCase++) {
int N = Integer.parseInt(br.readLine());
String[] nodes = new String[N + 1];
int[] lefts = new int[N + 1];
int[] rights = new int[N + 1];
int index;
String value;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
switch (st.countTokens()) {
case 2:
index = Integer.parseInt(st.nextToken());
value = st.nextToken();
nodes[index] = value;
break;
case 3:
index = Integer.parseInt(st.nextToken());
value = st.nextToken();
nodes[index] = value;
lefts[index] = Integer.parseInt(st.nextToken());
break;
case 4:
index = Integer.parseInt(st.nextToken());
value = st.nextToken();
nodes[index] = value;
lefts[index] = Integer.parseInt(st.nextToken());
rights[index] = Integer.parseInt(st.nextToken());
break;
}
}
Tree tree = new Tree(1, nodes[1]);
for (int i = 1; i <= N; i++) {
tree.makeLeftChild(i, lefts[i], nodes[lefts[i]]);
tree.makeRightChild(i, rights[i], nodes[rights[i]]);
}
sb.append("#").append(testCase).append(" ");
tree.inorder(tree.getRoot());
sb.append("\n");
}
System.out.println(sb);
}
}
나의 풀이
- 트리를 만들어서 풀었다.
- 입력 받는 걸 제대로 안해서 헤맸는데 디버깅으로 잘 잡았다.
- searchNode 같은 경우 null 값을 반환할 수도 있으므로 그 경우 curNode.을 사용할 수 없다. curNode가 null이 되기 때문이다.
- 이러한 포인트를 잘 잡자!!!
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘] 쿼드트리 (1) | 2024.02.14 |
---|---|
[알고리즘] 설탕 배달 (0) | 2024.02.13 |
[알고리즘] 절댓값 힙 (0) | 2024.02.07 |
[알고리즘][X] 색종이 (1) | 2024.02.06 |
[알고리즘] 큐 (0) | 2024.02.06 |