297. Serialize and Deserialize Binary Tree

Leetcode

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

題目

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

解答

• 方法一

用 BFS 的方式存 tree nodes

ex.

input => [1,2,3,null,null,4,5,6,7]

serialize => [1,2,3,null,null,4,5,null,null,null,null,6,7,null,null] (把所有空的子節點填 null)

deserialize =>[1,2,3,null,null,4,5,6,7]

但是這種方式如果很多節點都是 null，高度很深的樹的話會有問題，會存放很多不必要的 null 節點

[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9,null,10...] => 像這種樹就會 TLE

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    if (!root) return '';
    
    let data = '';
    const queue = [root];
    
    while(queue.length) {
        const length = queue.length;
        let temp = '';
        
        for(let i=0; i<length; i++) {
            const node = queue.shift();
            temp += node ? `${node.val};` : `null;`;
            queue.push(node?.left ?? null);
            queue.push(node?.right ?? null);
        }
        data += temp;
        if (queue.every(node => !node)) break;
    }
    
    return data.slice(0, -1);
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const arr = data.split(';');
    // console.log(arr);
    const length = arr.length;
    
    const map = new Map();
    const root = arr[0] ? new TreeNode(arr[0]) : null;
    map.set(0, root);
    
    const getNode = (index) => {
        if (map.has(index)) {
            return map.get(index);
        } else {
            const val = arr[index];
            const node = val === 'null' ? null : new TreeNode(arr[index]);
            map.set(index, node);
            return node;
        }
    }
    
    for(let i=0; i<length; i++) {
        const leftIndex = 2 * i + 1;
        const leftNode = getNode(leftIndex);
        
        const rightIndex = 2 * i + 2;
        const rightNode = getNode(rightIndex);
        
        const node = getNode(i);
        if (node) {
            node.left = leftIndex < length ? leftNode : null;
            node.right = rightIndex < length ? rightNode : null;
        }
    }
    
    return root;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

Time Limit Exceeded

• 方法二

使用 DFS 的方法

ex.

input => [1,2,3,null,null,4,5,6,7]

DFS => [1,2,3,4,6,7,5]

serialize => [1,2,null,null,3,4,6,null,null,7,null,null,5,null,null]

arr => [ '1', '2', 'null', 'null', '3', '4', '6', 'null', 'null', '7', 'null', 'null', '5', 'null', 'null', '' ]

deserialize =>[1,2,3,null,null,4,5,6,7]

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    const dfs = (node, str) => {
        if (node === null) {
            str += `${null},`;
        } else {
            const val = node.val;
            str += `${val},`;
            str = dfs(node.left, str);
            str = dfs(node.right, str);
        }
        return str;
    }
    
    return dfs(root, '');
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const dfs = (arr) => {
        const val = arr.shift();
        if (val === 'null') {
            return null;
        }
        
        const node = new TreeNode(val);
        node.left = dfs(arr);
        node.right = dfs(arr);

        return node;
    }
    
    const arr = data.split(',');
    // console.log(arr);
    return dfs(arr);
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

Runtime: 189 ms, faster than 42.05% of JavaScript online submissions for Serialize and Deserialize Binary Tree.

Memory Usage: 53.9 MB, less than 40.42% of JavaScript online submissions for Serialize and Deserialize Binary Tree.