前言

在上一期我们对二叉树的构造进行了深入的了解，重点掌握了构造的核心原理以及一些细节上面的问题。下面来学习二叉树的序列化，通过本篇文章你可以学会以下的题目

Leetcode
297.二叉树的序列化与反序列化

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

该题目本质上，就是把二叉树转换为字符串，再从字符串转为二叉树的过程。

至于我们序列化的过程，使用什么符号定义并不重要，只要最后能够反序列化出来即可。

对于一颗这样的树，我们可以将他序列化成2,1,#,6,3,#,#其实他考察的就是如何对二叉树进行遍历。

二叉树的递归遍历有三种，前序中序后序，迭代遍历有层序，那么就从层序开始，看如何解题

前序遍历解法

我们知道，前序遍历的代码就是在递归之前写的，那么就有以下的逻辑

1
2
3

if(!root)return '#';
traverse(root.left);
traverse(root.right);

那么我们就很容易得出序列化的过程了，就是字符串的连接

var serialize = function (root) {
    if(!root)return '#';
    return `${root},${serialize(root.left)},${serialize(root.right)}`;
}

反序列化

那么其实反序列化，就是把序列化的这一串字符串转换为treenode。

对于一个字符串来说，js提供了split方法帮我们进行分割，也就是说以下的逻辑，会分割出一个数组

1	const nodeArr = data.split(",");

我们拿到了这个数组，因为他是前序的序列化而来的，那么我们根据前序的特性可以得到以下条件

第一个值是根，这就是我们的递归关键，回想一下前序构造二叉树，我们可以得到如下的代码

const build = (preorder)=>{
  const val = preorder.shift();
  if(val === '#')return null;
  const root = new TreeNode(val);
  root.left = build(preorder);
  root.right = build(preorder);
  return root;
}

那么我们的反序列化就能写出来了

var deserialize = function (data) {
    const nodearr = data.split(",");
    if (!nodearr.length) return null;
    const build = (nodearr) => {
        const val = nodearr.shift();
        if (val === '#') return null;
        const root = new TreeNode(val);
        root.left = build(nodearr);
        root.right = build(nodearr);
        return root;
    }
    return build(nodearr);
};

完整代码

var serialize = function (root) {
    if (!root) {
        return '#'
    }
    return `${root.val},${serialize(root.left)},${serialize(root.right)}`
};

var deserialize = function (data) {
    const nodearr = data.split(",");
    if (!nodearr.length) return null;
    const build = (nodearr) => {
        const val = nodearr.shift();
        if (val === '#') return null;
        const root = new TreeNode(val);
        root.left = build(nodearr);
        root.right = build(nodearr);
        return root;
    }
    return build(nodearr);
};