Leetcode-297-Serialize and Deser

这是一道很开放的题目，实质上是要求我们设置一个编码和解码过程来存储和复现一颗树，传统的数据结构题目是怎么出的呢？给定中序遍历的序列+前序or后序or层序的序列，要求我们复现一棵树，那这题不就是直接读取给定树的中序和前序序列以实现存储吗？要求复原树的时候由中序+前序构造一棵树不就行了？

有趣的是这题要求的存储格式是字符串，因此我们只需要设置好间隔符，然后依次将中序序列和前序序列加入字符串，最后记录下树的结点个数放在字符串末尾就行了，这样我们还原树的时候只需要先读取字符串末尾的数字，然后将字符串剩余部分分成等长的两部分就行了。

由于思路过于直白，所以我有点懒得写，看了下Discuss区诸位大神的解法，发现了这题的有趣之处。我看到https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74252/Clean-C%2B%2B-solution的解法居然只用前序遍历就把树还原出来了，刚看到这个解法的时候有点懵逼，这和我学过的不一样啊……细看才发现这和普通的前序遍历还是有差异的，因为这个前序遍历序列存放了各个叶子结点的空子节点。

记录下这些空结点有什么作用呢？就拿上图的例子来说，这棵树用带空结点的前序遍历序列表示可以写成：

我们建树的时候采用递归的方式会如何呢？

函数分为两部分：

（1）边界条件

如果当前读取的字符为“null”，则返回nullptr。

（2）创建节点并继续遍历剩余部分

创建结点，赋值为当前字符代表的值，然后递归的建立左子树和右子树。

可以看到，相比传统的前序遍历序列，带空结点的前序遍历序列可以帮助我们知道左右子树在何时建立完成，比如这个例子中，根结点的左子树的根结点值为2，其左子树为空，右子树为空，因此我们知道，整棵树的左子树至此就建立完成了，这样就不会出现一个序列对应多棵可能树的情况。

具体实现代码如下（https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74252/Clean-C%2B%2B-solution）

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return "#";
        return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return mydeserialize(data);
    }
    TreeNode* mydeserialize(string& data) {
        if (data[0]=='#') {
            if(data.size() > 1) data = data.substr(2);
            return nullptr;
        } else {
            TreeNode* node = new TreeNode(helper(data));
            node->left = mydeserialize(data);
            node->right = mydeserialize(data);
            return node;
        }
    }
private:
    int helper(string& data) {
        int pos = data.find(',');
        int val = stoi(data.substr(0,pos));
        data = data.substr(pos+1);
        return val;
    }
};