[LeetCode]297. Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree - LeetCode

• 직렬화는, 어떤 자료구조 or 객체를, 일련의 bits로 변환하는 과정이다. 이렇게 하면, 파일이나 메모리 버퍼에 저장될 수 있거나, 네트워크 connection link를 통해 전송되어, 다른 host에서 다시 재조립 할 수가 있어진다.
• 이진트리를 직렬화하고, 역직렬화하라. 여기에 다른 제한은 없지만
  • 직렬화 : 이진트리 → 문자열
  • 역직렬화 : 문자열 → 원래의 트리구조

아하 이제까지 리트코드에서 Tree문제가 나올 때 마다 [1,2,3,null,null,4,5] 이런식으로 주어졌는데 이형태로 만들라는 것.

문제풀이 ( bfs)

(100)

이문제에서 중요한 것은,

결국 같은 레벨의 것들을 먼저 처리해야 한다는 것이었다. → 따라서 BFS를 사용하였다.

• 직렬화
  • 맨 앞에서 “[” 를 가진 sb 를 만들어 놓고
  • 중간에 ~~~ 하고 나서
  • “]” 를 덧 붙인다.
• 중간에 ~~ ? 과정

left → right 순으로 출력하는데, null 이면 null이라고 출력한다.

• 그런데 이 때, left, right 모두가 null이어도 출력하는 거네

  • 이건 LeetCode에서 직렬화 표기위해 사용하는 방법 참고 → where null signifies a path terminator where no node exists below.

    What does [1,null,2,3] mean in binary tree representation?

---

• 역직렬화

문자열 문제가 됨

1. [랑 ] 를 벗겨내고
2. , 단위로 split ⇒ arr에 집어 넣는다.

• 몇 번째 글자를 추적하고 있는지 알기 위해 arr에 대한 idx 변수를 둔다.

• 역직렬화에서 역시 bfs를 사용해야하는 것 같다. 왜냐하면, [ 직렬화된 문자열이 root를 제외하고는, 항상 같은 레벨의 node에 대한 left, right 정보로 주어지기 때문임 ]

  • 그런데 이 때, q 에서 꺼낸 노드의 left, right 가 null이면 ( 즉, arr[idx].equals(”null”) 이면, q에 넣지 않는다 )

• 내가 고민했던 부분은, 현재 나의 풀이방식대로라면, 문제에서는 [1,2,3,null,null,4,5] 를 요구하는 부분이 [1,2,3,null,null,4,5,null,null,null,null] 이 나오게 된다는 것이었다. 하지만 문제를 자세히 읽어보니 이것도 괜찮았던것은 채점방식 때문이었음.

  • 채점 방식이 TreeNode ans = deser.deserialize(ser.serialize(root)); 였기 때문에, null 을 저대로 두어도, 그저 일반적인 TreeNode가 생성될 뿐이기 때문

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    public ArrayDeque<TreeNode> dq = new ArrayDeque<>(10000);
    public StringBuilder sb = new StringBuilder("[");
    public String serialize(TreeNode root) {
        if(root != null){
            sb.append(Integer.toString(root.val));
            dq.add(root);
            TreeNode temp;
            while(!dq.isEmpty()) {
                temp = dq.poll();

                // left
                sb.append(",");
                if (temp.left == null) sb.append("null");
                else {
                    sb.append(Integer.toString(temp.left.val));
                    dq.add(temp.left);
                }
                //right
                sb.append(",");
                if (temp.right == null) sb.append("null");
                else {
                    sb.append(Integer.toString(temp.right.val));
                    dq.add(temp.right);
                }
            }
        }
        sb.append("]");
        return sb.toString();
    }
		// util 함수 
    public TreeNode createNode(String str){
        return new TreeNode(Integer.parseInt(str));
    }
    public ArrayDeque<TreeNode> deque = new ArrayDeque<>(10000);
    public String[] arr;
    public TreeNode deserialize(String data) {
        // [] 인 경우
        if(data.length()==2) return null;
        data = data.substring(1,data.length()-1);
        arr = data.split(",");
        int idx = 0;
        TreeNode root = createNode(arr[idx++]);
        TreeNode temp;
        deque.add(root);
        while(idx < arr.length){
            temp = deque.poll();
            // left
            if(arr[idx].equals("null"));
            else{
                temp.left = createNode(arr[idx]);
                deque.add(temp.left);
            }
            idx++;
            //right
            if(arr[idx].equals("null"));
            else{
                temp.right = createNode(arr[idx]);
                deque.add(temp.right);
            }
            idx++;
        }
        return root;
    }
}

// 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));

다른 풀이 (dfs)

나는 serialize 결과 역시 [1,2,3,null,null,4,5] 이런 형태로 나와야한다고 생각했어서 계속해서 bfs를 사용하였다.

하지만, 문제에서 원하는 것은 어떤 serialize 결과를 → deserialize만 잘 시키면 됐음. 그리고 deserialize 결과로는 그저, 옳바른 이진트리를 만들기만 하면 되는 거였음.

따라서, dfs 로도 풀 수 있는 문제였음.