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

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：

• 树中结点数在范围[0, 10^4]内
• -1000 <= Node.val <= 1000

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

这里采用先序遍历记录二叉树的节点，如果为空则记录’#'作为标识（这就是序列化和遍历的区别。需要有两种遍历的结果才能确定一颗二叉树，而序列化时采用一种即可。因为序列化记录空树，而遍历不记录。

序列化时采用递归，不同节点的值之间用空格分隔。c++中分割带空格的字符串用istringstream，之后和序列化一样，递归地构造二叉树即可。

/**
 * 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:

    // 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) {
        istringstream is(data);
        return decode(is);
    }

    TreeNode* decode(istringstream& is){
        string tmp;
        is >> tmp;
        if(tmp == "#"){
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(tmp));
        root->left = decode(is);
        root->right = decode(is);
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));