二叉树的序列化与反序列化

06/30/2021

leetcode-二叉树的序列化与反序列化

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

树中结点数在范围 [0, 10⁴] 内
-1000 <= Node.val <= 1000

本人题解

/*
 * Encodes a tree to a single string.
 */
function serialize(root: TreeNode | null): string {
    let result:string = ''
    let nextNodes: TreeNode[] = [root]
    while (nextNodes.length > 0) {
        let curNodes: TreeNode[] = [];
        let curResult:(Number | String)[] = []
        nextNodes.forEach(node => {
            if (node) {
                curResult.push(node.val)
                curNodes.push(node.left, node.right)
            } else {
                curResult.push(' ')
            }
        })
        nextNodes = curNodes;
        result += curResult.join(',')
        if (nextNodes.length > 0) result+='|'
    }
    return result
};
 
/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
    let result:TreeNode = new TreeNode();
    let curNodes:TreeNode[] = [result]
    let lines:string[] = data.split('|')
    let firstV:string = lines.shift();
    if (firstV == ' ') {
        return null
    } else {
        result.val = parseInt(firstV);
        lines.forEach(l => {
            let nextNodes = [], curNode:TreeNode;
            let vals = l.split(',');
            vals.forEach((v, i) => {
                let r = i % 2 == 0 ? 'left' : 'right' ;
                curNode = r == 'left' ? curNodes.shift() : curNode;
                if (v != ' ') {
                    let newNode = new TreeNode(parseInt(v))
                    curNode[r] = newNode;
                    nextNodes.push(newNode)
                }
            })
            curNodes = nextNodes;
        })
    }
    return result
};

分析

忘了。以后再补