实用算法题: 二叉树序列化与反序列化
ChenYang Lv1
  2022-02-15 16:46:20 2022-02-15 16:46  

⛳ 实用算法题系列第二篇 - 二叉树序列化与反序列化。

🐼 先看原题

🦄 思路

虽然标签上是困难题，但实际上可以拆解成两个中等题，二叉树前序遍历 + 前序遍历二叉树。借鉴labuladong对二叉树遍历的总结：

1
2
3
4
5
6
7
8
9
10
11
12
const traverse = (root) => {
    if (root === null) {
        return;
    }

    // 前序遍历位置
    traverse(root.left);
    // 中序遍历位置
    traverse(root.right);
    // 后续遍历位置
};

💡 一般说的前中后序遍历，都是针对根节点而言。即前序遍历 -> 根左右，中序遍历 -> 左根右，后序遍历 -> 左右根。

因此，算法题的序列化代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var serialize = function (root) {
    return rsEncode(root, '');
};

const rsEncode = (root, str) => {
    if (root === null) {
        str += '#,';
    } else {
        // 前序遍历
        str += `${root.val},`;
        str = rsEncode(root.left, str);
        str = rsEncode(root.right, str);
    }
    return str;
}

通过序列化我们可以得到一串字符串，代表二叉树前序遍历结果。接下来，我们需要对其进行反序列化，重新生成二叉树。一般来讲，我们只有前序遍历结果无法还原二叉树，原因是不能确定空节点位置，而本题可以生成，因为我们将空节点用#表示。

按照前序遍历特性，字符串的首字符就是根节点，反序列化代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var deserialize = function (data) {
    const dataArr = data.split(',');
    if (dataArr.length === 0) {
        return null;
    }
    return rsDecode(dataArr);
};

const rsDecode = (arr) => {
    if (arr[0] === "#") {
        arr.shift()
        return null;
    }
    const cur = arr.shift();
    const root = new TreeNode(parseInt(cur));
    root.left = rsDecode(arr);
    root.right = rsDecode(arr);
    return root;
}

🎈 算法使用场景：JSON

JSON是一种跨语言工具，在JS中我们可以使用JSON.stringfy(), JSON.parse() 实现对值的序列化和反序列化。

💡 结尾

😂 字节跳动的面试官曾问过，如何将JavaScript语言的代码转成Java / C++，JSON不是面试官期望的答案。我想JSON只是一种序列化和反序列化的一种实现方式，可能面试官期望的是实现原理，有时间我会专门写一篇博客分析JSON的原理。