LeetCode 297. 二叉树的序列化与反序列化    原题链接    困难

作者： 作者的头像   wzc1995 ,  2018-06-20 12:33:22 ,  所有人可见 ,  阅读 3244

5


1

题目描述

序列化是将一个数据结构或对象转换成二进制序列使其能够存储在文件或内存缓冲区，或者通过网络链接传递。之后可以在相同或另一个计算机环境中重新构造该对象。

设计一个算法实现序列化和反序列化一个二叉树，序列化和反序列化的算法没有限制，只需要保证可以将二叉树序列化为字符串，然后该字符串可以被反序列化为原始的树结构。

注意

  • 不得使用类成员、全局或者静态变量存储状态，序列化和反序列化算法不能和状态有关。

样例

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示

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

说明

  • 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

算法

(先序遍历序列化) $O(n)$
  1. 我们按照先序遍历，即可完整唯一的序列化一棵二叉树。但空结点需要在序列化中有所表示。
  2. 例如样例中的二叉树可以表示为 1,2,(null),(null),3,4,(null),(null),5,(null),(null),。这里的 (null) 仅做示意，并不是真正序列化出字符串 (null)。
  3. 通过先序遍历序列化该二叉树；反序列化时，按照 , 作为分隔，构造当前结点后分别通过递归构造左右子树。

时间复杂度

  • 每个结点仅遍历两次，故时间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    void solve(TreeNode* root, string& s) {
        if (root == NULL) {
            s += ",";
            return;
        }

        s += to_string(root->val) + ",";

        solve(root->left, s);
        solve(root->right, s);
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        solve(root, s);
        return s;
    }

    TreeNode* decode(int &cur, const string& data) {
        if (data[cur] == ',') {
            cur++;
            return NULL;
        }

        int nxt = data.find(',', cur);
        int val = stoi(data.substr(cur, nxt - cur));

        TreeNode *r = new TreeNode(val);
        cur = nxt + 1;

        r->left = decode(cur, data);
        r->right = decode(cur, data);

        return r;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int cur = 0;
        return decode(cur, data);
    }
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

19 评论

用户头像
有心人   2021-07-08 18:32         踩      回复

提问:
大神，想请教一下，反序列化 decode() 中 为什么 遍历data到最后 不用判断 if (cur == data.size()) return NULL; 呢？想好像能明白，但是 感觉 还是 有点难以用语言表达出来，请问能 用文字描述一下原因吗？

用户头像
wzc1995   2021-07-09 23:09         踩      回复

没必要判断，以为保证序列化的字符串就是一颗合法的树，按照规则反序列化不会出问题

用户头像
有心人   2021-07-10 08:24    回复了 wzc1995 的评论         踩      回复

好的，谢谢~

用户头像
ninglei   2021-09-15 03:41    回复了 wzc1995 的评论         踩      回复

难道不会越界？

用户头像
wzc1995   2021-09-15 16:24    回复了 ninglei 的评论         踩      回复

不会

用户头像
灬时空转角盛夏落幕   2020-04-23 10:50         踩      回复

请问一下为什么要加&符号

用户头像
wzc1995   2020-04-25 08:55         踩      回复

& 在参数里是引用，可以看做全局变量

用户头像
hpysirius   2019-08-18 12:50         踩      回复

### JS的语法


var serialize = function (root) {
    let res = '';
    const dfs1 = (root) => {
        if (!root) {
            res += '#,';
            return;
        }
        res += root.val + ',';
        dfs1(root.left);
        dfs1(root.right);
    }
    dfs1(root);
    return res;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
    let u = 0;

    const dfs2 = (data) => {
        if (data[u] === '#') {
            u += 2;
            return null;
        }
        let t = 0;
        let is_minus = false;
        if (data[u] === '-') {
            is_minus = true;
            u++;
        }
        while (data[u] !== ',') {
            t = t * 10 + (data[u] - '0');
            u++;
        }
        u++;
        if (is_minus) t = -t;
        let root = new TreeNode(t);
        root.left = dfs2(data);
        root.right = dfs2(data);
        return root;
    }

    return dfs2(data, u);
};
用户头像
ziphe   2019-08-05 16:57         踩      回复

找到原因了str += “,”不能写成str = str + “,”

用户头像
ziphe   2019-08-05 16:37         踩      回复

求帮忙看下，我这个代码和您的基本一样，为什么总是内存溢出呀
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res = “”;
PreOrderTraversal(root, res);

    return res;
}
void PreOrderTraversal(TreeNode* root,string& res)
{
    if(!root)
    {
        res = res + "#,";
        return;
    }
    res = res + to_string(root->val) + ',';
    PreOrderTraversal(root->left, res);
    PreOrderTraversal(root->right, res);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    int index = 0;

    return reConstruction(data, index);
}
TreeNode* reConstruction(const string& data, int& index)
{
    if (data[index] == '#') {
        index += 2;
        return nullptr;
    }
    int nxt = data.find(',', index);
    int val = stoi(data.substr(index, nxt - index));
    TreeNode *root = new TreeNode(val);
    index = nxt + 1;

    root->left = reConstruction(data, index);
    root->right = reConstruction(data, index);

    return root;
}
用户头像
Julinkgo   2019-07-26 15:14         踩      回复

在反序列化的的时候，不用考虑cur到达字符串尾端的问题吗

用户头像
wzc1995   2019-07-27 12:41         踩      回复

合法的字符串不会出现cur越界的情况

用户头像
Jax   2019-07-21 17:40         踩      回复

decode函数定义的参数中为什么要加一个const呢

用户头像
wzc1995   2019-07-22 07:17         踩      回复

说明 data 本身是不可修改的

用户头像
Jax   2019-07-22 11:32    回复了 wzc1995 的评论         踩      回复

好的

用户头像
wzc1995   2018-08-04 23:08         踩      回复

string::find 是 string类的一个成员函数，详情可以参考 string::find。
至于 istringstream 和 ostringstream，我不太清楚，但 string 已经是 C++ 功能比较强大的类了。

用户头像
小雨   2018-08-04 07:20         踩      回复

int nxt = data.find(‘,’, cur); 这一行代码感觉看得不是很懂诶， 直接用string 会比较好么，看到另外一个解法是用的istringstream 和 ostringstream, 感觉那种看起来会好看一点。不过直接这么用也许有直接用的好处吧

用户头像
徐辰潇   2018-12-10 02:15         踩      回复

所以用instringstream 怎么写啊？？能麻烦上传一下code吗，很好奇想看一下==谢谢

用户头像
song666   2019-07-30 14:17    回复了 徐辰潇 的评论         踩      回复

我的代码就用的是istringstream，这里有代码

//这道题LeetCode是层序遍历的，但是怕麻烦写了一个先序遍历的极水代码
class Codec {
    public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        serialize(root, out);
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserialize(in);
    }

    private:

    void serialize(TreeNode* root, ostringstream& out)
    {
        if (root != NULL)
        {
            out << root -> val << ' ';
            serialize(root -> left, out);
            serialize(root -> right, out);
        }
        else out << "# ";
    }

    TreeNode* deserialize(istringstream& in)
    {
        string val;
        in >> val;
        if (val == "#") return NULL;
        TreeNode* root = new TreeNode(stoi(val));
        root -> left = deserialize(in);
        root -> right = deserialize(in);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));