[Grind75-LeetCode] Serialize and Deserialize Binary Tree - Hard
접근
- 전위 순회
풀이
이진트리의 직렬화, 역직렬화를 구현하는 문제이다. 직렬화란 프로그램 내에서 복잡한 데이터 구조인 객체, 트리, 그래프 등을 바이트 스트림 또는 문자열 형태로 변환하여 파일에 저장하거나 네트워크를 통해 전송할 수 있게 하는 개념이다. 복잡한 데이터를 일관된 형식으로 표현하여 직렬화 한 뒤 데이터를 전송하고 받은 직렬화된 데이터를 역직렬화하여 데이터 구조를 복원하여 사용한다.
이번 문제는 이진트리의 직렬화 과정과 역직렬화 과정을 구하는 문제인데 주어진 코드는 문자열 직렬화이지만 채점 기준으로 각 직렬화, 역직렬화를 통해 동일한 값을 얻을 수 있느냐 즉 정상적으로 직렬화와 역직렬화가 수행이 되는지를 기준으로 채점하기 때문에 각자의 다양한 방식을 통해 풀 수 있는 문제이다. 그렇다 보니 실제 직렬화와 역직렬화 과정을 수행하지 않고 객체를 보관했다 그대로 넘겨주는 꼼수 코드도 존재했다.
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
public class Codec {
static TreeNode node;
public String serialize(TreeNode root) {
node = root;
return "";
}
public TreeNode deserialize(String data) {
return node;
}
}주석의 내용과 같이 호출되어 채점이 이루어지다 보니 직렬화된 트리의 값으로 역직렬화를 했을 때 원본과 동일한지 체크를 하게 되는데 직렬화된 값이 어떤 값이든 상관없이 마지막에 역직렬화된 값만 원본과 동일하다면 맞다는 점을 이용한 꼼수 코드가 존재했다.
아무튼 직렬화와 역직렬화는 암호화 복호화 과정과 같다고 생각하면 되기 때문에 나만의 기준을 가지고 문제를 풀면 된다. 문자열을 통해 직렬화하는데 문제에서 주어진 output과 동일한 형태로 "1,2,3, null, null,4,5" 쉼표를 통해 각 노드를 구분하고 전위 순회를 통해 직렬화를 수행해 줬다.
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("null,");
} else {
sb.append(node.val).append(",");
serialize(node.left, sb);
serialize(node.right, sb);
}
}실제 직렬화를 수행하는 코드를 오버로딩하여 구현해 줬는데 StringBuilder를 사용해 직렬화 문자열을 만들어줬다. 만드는 과정은 전위 순회로 루트 -> 왼쪽 -> 오른쪽 순으로 탐색을 하며 문자열에 추가해 줬다. 해당 자리의 노드가 없는 경우 null을 삽입해 줬고 노드가 존재한다면 노드의 값을 추가하고 쉼표를 넣은 뒤 루트 -> 왼쪽 -> 오른쪽 순으로 재귀를 통해 트리의 모든 노드를 직렬화한다.
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] nodes = data.split(",");
Queue<String> queue = new LinkedList<>(Arrays.asList(nodes));
return deserialize(queue);
}
private TreeNode deserialize(Queue<String> queue) {
String value = queue.poll();
if (value.equals("null")) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(value));
node.left = deserialize(queue);
node.right = deserialize(queue);
return node;
}다음은 역직렬화 과정이다. 직렬화된 문자열을 쉼표를 기준으로 잘라준 뒤 큐에 넣어준다. 큐에서 하나씩 뽑으며 다시 트리를 만들어주게 된다. 값으로 null이 들어있는 경우 null 노드를 반환하고 값이 있다면 해당 값으로 노드를 만들어준 뒤 그 노드의 각 왼쪽 오른쪽 자식도 동일하게 역직렬화시켜준다. 전위 순회를 통해 직렬화했기 때문에 역직렬화도 동일하게 전위 순회를 따라 수행해 주게 된다.
2ms
문제에 대한 기준이 애매하기 때문에 풀어진 다른 코드를 하나 분석하고 넘어가겠다. 이 코드는 트리 각 노드의 값에 특정 값을 더한 뒤 자식이 있는지와 직렬화 마무리 여부를 각 플래그를 통해 알리는 방식으로 만들어졌다.
public class Codec {
private static int index;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelper(sb, root);
return sb.toString();
}문자열 직렬화인만큼 동일하게 StringBuilder를 사용해 구현된다. 차이점으론 index 필드가 전역으로 선언되어 있다.
private static void serializeHelper(StringBuilder sb, TreeNode node) {
if (node == null) {
return;
} else {
sb.append((char) (node.val + 1024));
}
if (node.left != null) {
sb.append('l');
serializeHelper(sb, node.left);
}
if (node.right != null) {
sb.append('r');
serializeHelper(sb, node.right);
}
sb.append('p');
}직렬화 과정이다. 노드가 존재하지 않는다면 직렬화를 종료한다. 노드가 존재한다면 해당 노드의 값에 1024를 더한 값으로 저장한다. 노드의 값이 1이라면 해당 노드의 값으로 1025에 해당하는 char가 저장되는데 역직렬화 과정에서 하나의 인덱스로 다루기 위해 숫자의 형태가 아닌 대응되는 char의 값으로 저장하게 된다. 그리고 해당 노드의 왼쪽 서브트리가 존재한다면 l이라는 문자를 삽입하고 왼쪽 서브트리에 대해서도 똑같이 직렬화를 진행한다. 오른쪽 서브트리가 존재한다면 r을 삽입하고 동일한 방법으로 진행하고 직렬화가 모두 끝났다면 마지막에 p를 삽입하여 끝남을 표시하게 된다.
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
index = 0;
return deserializeHelper(data);
}역직렬화 코드이다. 각 레벨을 위해 index를 초기화하고 직렬화를 수행한다.
private static TreeNode deserializeHelper(String data) {
if (index >= data.length() - 1) {
return null;
}
int val = data.charAt(index) - 1024;
index += 1;
TreeNode node = new TreeNode(val);
if (data.charAt(index) == 'l') {
index += 1;
node.left = deserializeHelper(data);
}
if (data.charAt(index) == 'r') {
index += 1;
node.right = deserializeHelper(data);
}
if (data.charAt(index) == 'p') {
index += 1;
}
return node;
}역직렬화 과정으로 인덱스가 데이터의 길이를 넘어가게 되면 null을 반환한다. 직렬화된 문자열에서 인덱스로 값을 뽑아 1024를 빼 원래 값으로 만들어준 뒤 하나의 노드 처리가 끝났음을 알리기 위해 index 값을 증가시켜 준다. 그리고 만약 다음 인덱스의 값이 l이나 r이라면 해당 노드의 서브트리가 존재한다는 뜻으로 서브트리에 대한 처리를 진행해주고 p 표시를 만나게 되면 역직렬화가 끝난것으로 인덱스 값을 증가시킨다.
전체 코드
전위 순회
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append("null,");
} else {
sb.append(node.val).append(",");
serialize(node.left, sb);
serialize(node.right, sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] nodes = data.split(",");
Queue<String> queue = new LinkedList<>(Arrays.asList(nodes));
return deserialize(queue);
}
private TreeNode deserialize(Queue<String> queue) {
String value = queue.poll();
if (value.equals("null")) {
return null;
}
TreeNode node = new TreeNode(Integer.parseInt(value));
node.left = deserialize(queue);
node.right = deserialize(queue);
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
큐 사용 x
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
private static int index;
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeHelper(sb, root);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
index = 0;
return deserializeHelper(data);
}
private static void serializeHelper(StringBuilder sb, TreeNode node) {
if (node == null) {
return;
} else {
sb.append((char) (node.val + 1024));
}
if (node.left != null) {
sb.append('l');
serializeHelper(sb, node.left);
}
if (node.right != null) {
sb.append('r');
serializeHelper(sb, node.right);
}
sb.append('p');
}
private static TreeNode deserializeHelper(String data) {
if (index >= data.length() - 1) {
return null;
}
int val = data.charAt(index) - 1024;
index += 1;
TreeNode node = new TreeNode(val);
if (data.charAt(index) == 'l') {
index += 1;
node.left = deserializeHelper(data);
}
if (data.charAt(index) == 'r') {
index += 1;
node.right = deserializeHelper(data);
}
if (data.charAt(index) == 'p') {
index += 1;
}
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글
| [Grind75-LeetCode] Find Median from Data Stream JAVA (0) | 2024.11.30 |
|---|---|
| [Grind75-LeetCode] Trapping Rain Water JAVA (1) | 2024.11.29 |
| [Grind75-LeetCode] Minimum Window Substring JAVA (0) | 2024.11.27 |
| [Grind75-LeetCode] Kth Smallest Element in a BST JAVA (0) | 2024.11.26 |
| [Grind75-LeetCode] LRU Cache JAVA (0) | 2024.11.25 |