https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
이진 트리에 대한 직렬화, 역직렬화를 구현하는 문제다.
이진트리는 배열로도 레벨 별 요소를 표현할 수 있다는 점을 활용하면 될 것 같다.
예를 들어 [1,2,3,null,null,4,5]
에서
~0번: level1, 요소 1개
~2번: level2, 요소 2개
~6번: level3, 요소 4개
이런 규칙으로 요소가 2의 거듭제곱으로 늘어나는 것을 볼 수 있다.
역직렬화 시 이 규칙을 통해 레벨 별 요소를 넣어줄 수 있을 거로 보인다.
풀다 보니 빵꾸난 부분이 꼭 null로 채워지진 않는듯;;
직렬화, 역직렬화 모두 Queue 이용해서 순회하도록 했다.
특히, 역직렬화는 배열 기준으로 index++하면서 요소를 찾아나가는 데에 집중했고,
직렬화의 경우 좌측부터 순서대로 넣는 것에 집중했으며 리프인 경우 하위 레벨 노드들 모두 "null"로 채워넣지 않게 방어처리 하는데 집중했다.
결과적으로 아래 코드로 정답이 나오기는 했는데, 개선해야 할 점이 많은듯
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "[]";
}
StringBuilder sb = new StringBuilder("[");
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
int size = que.size();
boolean hasChild = false;
List<TreeNode> nextNodes = new ArrayList<>();
for (int i=0; i<size; i++) {
TreeNode node = que.poll();
if (node == null) {
sb.append("null,");
} else {
sb.append(node.val + ",");
nextNodes.add(node.left);
nextNodes.add(node.right);
hasChild = hasChild || node.left != null || node.right != null;
}
}
if (hasChild) {
que.addAll(nextNodes);
}
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String body = data.substring(1, data.length() - 1);
if (body.isEmpty()) {
return null;
}
String[] elements = body.split(",");
int rootValue = Integer.parseInt(elements[0]);
Queue<TreeNode> que = new LinkedList<>();
TreeNode root = new TreeNode(rootValue);
que.offer(root);
int index = 1;
while (!que.isEmpty() && index < elements.length) {
int size = que.size();
for (int i=0; i<size; i++) {
TreeNode node = que.poll();
String leftValue = elements[index++];
String rightValue = elements[index++];
if (!leftValue.equals("null")) {
node.left = new TreeNode(Integer.parseInt(leftValue));
que.offer(node.left);
}
if (!rightValue.equals("null")) {
node.right = new TreeNode(Integer.parseInt(rightValue));
que.offer(node.right);
}
}
}
return root;
}
}
GPT한테 피드백을 좀 받아보자.
아래는 GPT가 리팩터링 해준 코든데, 핵심을 요약하면 아래와 같다.
,
넣는 타이밍 수정 - i > 0
일 때만 앞에 붙여주면 더 직관적이고 추후에 잘라낼 필요도 없음public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) return "[]";
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// 토큰을 리스트에 모았다가 뒤쪽의 "null" 연속 구간 제거
List<String> tokens = new ArrayList<>();
while (!q.isEmpty()) {
TreeNode node = q.poll();
if (node == null) {
tokens.add("null");
} else {
tokens.add(String.valueOf(node.val));
q.offer(node.left);
q.offer(node.right);
}
}
// 뒤에서부터 연속된 "null"을 제거
int last = tokens.size() - 1;
while (last >= 0 && "null".equals(tokens.get(last))) last--;
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 0; i <= last; i++) {
if (i > 0) sb.append(',');
sb.append(tokens.get(i));
}
sb.append(']');
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data == null || data.length() < 2) return null;
String body = data.substring(1, data.length() - 1);
if (body.isEmpty()) return null;
String[] arr = body.split(",");
if (arr.length == 0 || "null".equals(arr[0])) return null;
TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
int i = 1;
while (!q.isEmpty() && i < arr.length) {
TreeNode parent = q.poll();
// left
if (i < arr.length && !"null".equals(arr[i])) {
TreeNode left = new TreeNode(Integer.parseInt(arr[i]));
parent.left = left;
q.offer(left);
}
i++;
// right
if (i < arr.length && !"null".equals(arr[i])) {
TreeNode right = new TreeNode(Integer.parseInt(arr[i]));
parent.right = right;
q.offer(right);
}
i++;
}
return root;
}
}