(Leetcode) 297 - Serialize and Deserialize Binary Tree
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
주간 미션을 마쳤기 때문에 시간이 남아서 뒤 한문제를 골라 풀기로 하였다.
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
하드 문제임에도 풀긴 하였으나, 거의 아슬아슬하게 풀었다.
먼저 직접 작성한 풀이에 대해 정리해보고 다른 사람이 작성한 풀이도 정리해본다.
내가 작성한 풀이
문제에서 다음과 같은 TreeNode를 쓰도록 제공하고 있다.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
Codec 부분의 코드는 다음과 같다.
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> output = new ArrayList<>();
if (root != null) {
queue.offer(root);
}
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
output.add(node.val);
queue.add(node.left);
queue.add(node.right);
} else {
output.add(null);
}
}
return Arrays.toString(output.toArray());
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String removeBraket = data.substring(1, data.length() - 1);
String[] nodeVals = removeBraket.replaceAll(" ", "").split(",");
if (removeBraket.isEmpty()) {
return null;
}
List<TreeNode> nodeList = new ArrayList<>();
for (int i = 0; i < nodeVals.length; i++) {
String nodeValString = nodeVals[i];
nodeList.add(nodeValString.equals("null") ? null : new TreeNode(Integer.parseInt(nodeValString)));
}
int pointer = 0;
for (int i = 0; i < nodeVals.length; i++) {
if (pointer == i) {
continue;
}
while (nodeList.get(pointer) == null) {
pointer++;
}
TreeNode newNode = nodeList.get(i);
if (newNode == null) {
TreeNode nextNode = nodeList.get(i + 1);
if (nodeList.get(pointer).left == null) {
nodeList.get(pointer).left = newNode;
nodeList.get(pointer).right = nextNode;
pointer++;
i++;
} else if (nodeList.get(pointer).right == null) {
nodeList.get(pointer).right = newNode;
pointer++;
}
} else {
if (nodeList.get(pointer).left == null) {
nodeList.get(pointer).left = newNode;
} else if (nodeList.get(pointer).right == null) {
nodeList.get(pointer).right = newNode;
pointer++;
}
}
}
return nodeList.getFirst();
}
}
당황스러웠던 부분
serialize format
[1,2,3,null,null,4,5,6,7]
위의 배열을 처음 봤을 때 이상하다는 생각이 들었다. 내가 예상하지 못한 갯수가 들어왔기 때문이다.
내가 위 input을 보고 예상한 트리모양은 다음과 같았다. 딱봐도 트리 구조가 이상한 걸 알 수 있다.
하지만 leetcode 에서 제공되는 tree visualizer tool 을 통해 트리 모양을 확인해보면 다음과 같다.
비어있는 공간이 노드와 직접 연결되는 곳이 아니라면 null로 따로 표기하지 않는다는 것을 알게 되었고, 이에 따라 index를 통해 left 인지 right 인지 파악하는 로직을 제거하고 다른 방법을 고민해봐야 했다.
엣지케이스
[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10,null,11,null,12,null,13,null,14,null,15,null,16,null,17,null,18,null,19,null,20,null,21,null,22,null,23,null,24,null,25,null,26,null,27,null,28,null,29,null,30,null,31,null,32,null,33,null,34,null,35,null,36,null,37,null,38,null,39,null,40,null,41,null,42,null,43,null,44,null,45,null,46,null,47,null,48,null,49,null,50,null,51,null,52,null,53,null,54,null,55,null,56,null,57,null,58,null,59,null,60,null,61,null,62,null,63,null,64,null,65,null,66,null,67,null,68,null,69,null,70,null,71,null,72,null,73,null,74,null,75,null,76,null,77,null,78,null,79,null,80,null,81,null,82,null,83,null,84,null,85,null,86,null,87...
이런식으로 구성이 되면 한쪽으로 연결된 linked list와 같은 형태가 나온다.
TC, SC
serialized와 deserialized 모두 시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.
다른 사람의 풀이
public class Codec {
private static final String split = ",";
private static final String N = "X";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
helper(root, sb);
return sb.toString();
}
void helper(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(N).append(split);
return;
}
sb.append(node.val).append(split);
helper(node.left, sb);
helper(node.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> node = new LinkedList<>();
node.addAll(Arrays.asList(data.split(split)));
return helper2(node);
}
public TreeNode helper2(Deque<String> nodes) {
String val = nodes.remove();
if (val.equals(N)) {
return null;
}
TreeNode node = new TreeNode(Integer.valueOf(val));
node.left = helper2(nodes);
node.right = helper2(nodes);
return node;
}
}
이 코드는 실제와는 다른 구조로 serialize 하고 그에 따라 deserialize를 한다.
예를들어 [1,2,3,null,null,4,5,6,7] 이라는 입력이 들어오면 1,2,X,X,3,4,6,X,X,7,X,X,5,X,X, 형태로 serialize가 된다.
중간 형태를 체크하지 않기 때문에 가능한 풀이이라고 생각된다.
Deque 자료구조
java 에서는 Deque 라는 자료구조도 제공한다. 이 자료구조는 선형 자료구조이며, 사용자의 선택에 따라 Queue 처럼 사용할 수 있고, Stack 처럼 사용할 수도 있다. 덱 또는 데크 라고 불리는 것으로 보인다. (디큐 가 아니다.)
TC, SC
serialized와 deserialized 모두 시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.
참고
- how LeetCode serializes a binary tree
- tree visualizer tool
- 위 링크의 example에 값을 넣으면 어떤 모양으로 트리가 생성되는지 확인할 수 있다.