LeetCode HOT100 - 二叉树的序列化与反序列化

问题就是要把一个树压缩成一个序列，并且可以恢复

最直接的序列化实际上就是前序、后序这样的形式

在一般的二叉树的题中，需要前序+中序才能还原树

但是如果我们把 null 也存下来，那么一个前序实际上已经足够还原树的信息了

前序的顺序是 根->左->右

反序列化的时候，也是类似的，先建根节点，然后递归构建左子树和右子树

因为我们存了 null 的信息，所以当递归没法继续向下的时候，就知道该到右子树了

/*** 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 dfs1(TreeNode *root, string &s) {if (!root) {s += "#,";return;}s += to_string(root->val) + ",";dfs1(root->left, s);dfs1(root->right, s);}TreeNode* dfs2(vector<string> &a, int &u) {if (a[u] == "#") {u++;return nullptr;}TreeNode *root = new TreeNode(stoi(a[u]));u++;root->left = dfs2(a, u);root->right = dfs2(a, u);return root;}// Encodes a tree to a single string.string serialize(TreeNode* root) {string s;dfs1(root, s);return s;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {vector<string> a;string cur;for (auto c : data) {if (c == ',' ) {a.emplace_back(cur);cur.clear();} else {cur += c;}}int u = 0;return dfs2(a, u);}
};// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));