<Hard> Serialize and Deserialize Binary Tree (LeetCode : C#)

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

📕 문제 설명

주어진 데이터를 bit sequence로 변경하는 것을 serialization이라고 한다. 이진 트리를 serialize하고 deserialize하는 알고리즘을 설계하기 (함수 작성하는 문제)

serialize는 tree가 주어지면 string으로 변환하면 되며 deserialize는 string이 주어질 때 tree로 변환하면 된다.

+) string의 경우 다음의 형태이다.

• Input
  binary tree 정보, string 정보
• Output
  serialize, deserealize한 결과

예제

풀이

Serialize (tree -> string)은 예제의 Input처럼 TreeNode가 주어진다. root -> left -> right 순의 string을 만들기 위해서는 위의 string stdout처럼 만들어줘야한다. 간단하게 자기 자신의 값을 string에 붙인 다음 왼쪽을 재귀로 붙여나간 후 오른쪽 붙여나가면 1,2,n,n,3 .. 형태로 string이 만들어진다. 마지막 , 제거하고 return 하면 끝!

Deserialize (string -> tree)의 Input은 1,2,n,n,3,4, .. 식으로 주어진다. 문자열 그대로 주어지기 때문에 우선 ,를 기준으로 잘라낸 다음 제일 앞부터 뽑아내면서 트리 만들어야하므로 큐를 사용했다. 큐를 dequeue 하는 것을 재귀로 돌리면서 left 먼저 다 연결하고 다음은 right 연결하는 식으로 진행하면 된다.

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

    // tree를 string으로 변환
    public string serialize(TreeNode root) 
    {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        TreeSerialize(root, sb);
        return sb.ToString().TrimEnd(',');
    }

    private void TreeSerialize(TreeNode node, StringBuilder sb)
    {
        if (node == null)
        {
            sb.Append("n,"); // null이므로 n 추가 
            return;
        }

        sb.Append(node.val + ","); // 자신 추가
        TreeSerialize(node.left, sb); // left 추가
        TreeSerialize(node.right, sb); // right 추가 
    }

    // string을 tree로 변환 
    public TreeNode deserialize(string data) 
    {
        if (data == "") return null;
        Queue<string> q = new Queue<string>(data.Split(','));
        return TreeDeserialize(q);
    }

    private TreeNode TreeDeserialize(Queue<string> q)
    {
        string nodeVal = q.Dequeue();
        if (nodeVal == "n") return null; // null인 경우 
            
        TreeNode node = new TreeNode(int.Parse(nodeVal));
        node.left = TreeDeserialize(q); // left 먼저 dequeue 하면서 tree 연결 (n, n만나는 지점에서 끝나게 됨)
        node.right = TreeDeserialize(q); // n,n 만난 지점 이후가 right 되는 지점으로 동일하게 dequeue 하면서 연결 진행 

        return node;
    }
}

결과