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

点击：题目链接：序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

思路

由题意的，先将二叉树的所有节点转换成一个字符串或存储在一个连续的存储区域，然后再读取这个区域，将其转换成原来的二叉树。我们可以用前序，中序，后序三种顺序的任一一种。
这里使用的是前序遍历。

代码

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        dfs(root);
        return nodes;
    }

    void dfs(TreeNode* root) {
        if (root == nullptr) {
            nodes += "null,";
            return;
        }

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

        dfs(root->left);
        dfs(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        tmp = data;
        return de_dfs();
    }

    TreeNode* de_dfs() {
        int index = tmp.find(",");
        string cur = "";
        
        if (index > -1) {
            cur = tmp.substr(0, index);
            tmp.erase(0, index + 1);
        }
        else {
            //if the last string is not end with ","
            cur = tmp;
        }

        if(cur == "null" || cur=="") return nullptr;

        TreeNode* root = new TreeNode(stoi(cur));
        
        root->left = de_dfs();
        root->right = de_dfs();

        return root;
    }

private:
    string nodes;
    string tmp;
};

复杂度：
时间O（N）， 空间O（N）