Serialize and Deserialize BST

Serialize and Deserialize BST

- 문제 내용 : BST를 직렬화하고 이를 Deserialize 하여라

- 접근 방법

DFS를 통해서 node의 value를 String화 하고 이를 복구 하면서 다시 Node Tree를 만든다.

Serialize

상기와 같이 DFS 방식으로 1,2,4,null,3,null,5 순서로 String을 만들고 이를 다시 역직렬화 하면 된다.

역 직렬화

역직렬화시 주의해야 할 점은 직렬화되서 넘어온 값을 Queue로 하나씩 빼나가면서 처리 해야 한다는 것이다.

코드는 다음과 같다.

var serialize = function(root) {
    console.log(dfs(root));

    function dfs(node, queue = new Array()) {
        if(node == null) return "N";

        let result = node.val.toString();

        result += ',' + dfs(node.left);
        result += ',' + dfs(node.right);

        return result;
    }
};

var deserialize = function(data) {
    let queue = data.split(',');

    return deDfs();

    function deDfs() {
        let val = queue.shift();
        if (val === 'N') {
            return null;
        }
        let node = new TreeNode(val);

        node.left = deDfs();
        node.right = deDfs();

        return node;
    }

};

그러데 Javascript의 경우는 객체의 직렬화를 지원하는 함수가 있다. JSON을 통해서 처리 하면 되는데 이는 다음과 같이 짧아진 코드를 만들어 준다.

var serialize = function(root) {
    return JSON.stringify(root);
};

var deserialize = function(data) {
    return JSON.parse(data);

};

물론 알고리즘 테스트 임으로 쓸모는 없다.