题目
请实现两个函数，分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。
样例
你可以序列化如下的二叉树
8
/ \
12 2
/ \
6 4
为：”[8, 12, 2, null, null, 6, 4, null, null, null, null]”
注意:
以上的格式是AcWing序列化二叉树的方式，你不必一定按照此格式，所以可以设计出一些新的构造方式。

解法：前序遍历

前序遍历和层序遍历都可以
时间复杂度O(n)，空间复杂度O(1)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ans;
        dfs1(root, ans);
        return ans;
    }
    void dfs1(TreeNode* u, string &s) {
        if (!u) {
            s += "#,";
            return;
        }
        s += to_string(u->val) + ",";
        dfs1(u->left, s);
        dfs1(u->right, s);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int p = 0;
        return dfs2(data, p);
    }
    TreeNode* dfs2(string &s, int &p) {
        if (s[p] == '#') {
            p += 2;
            return nullptr;
        }
        bool minus = false;
        int num = 0;
        while (s[p] != ',') {
            if (s[p] == '-') minus = true;
            else num = num * 10 + s[p] - '0';
            p++;
        }
        p++;
        if (minus) num = -num;
        auto root = new TreeNode(num);
        root->left = dfs2(s, p);
        root->right = dfs2(s, p);
        return root;
    }
};