解法一：前序遍历

题目要求：1. 访问二叉树，并将访问结果存到一个字符串中返回，即：「二叉树的序列化」；2. 访问得到的字符串，重构出二叉树，即：「二叉树的反序列化」。

显而易见的是，在二叉树的序列化过程中，需要「遍历二叉树」，因此可采用二叉树的遍历方法之一：「前序遍历」来实现。这是因为：前序遍历是「先访问根结点」，再访问左子树，最后访问右子树。这在我们反序列化时，可以更容易地确定根结点的位置，因此采用前序遍历比中序遍历、后序遍历更为方便。

值得注意的是：

由于在反序列化时需要判断「当前结点是否为空」，因此在前序遍历进行序列化时，需要特殊标记空结点（'#'号）；
此外，为更方便地分辨出各个结点的值，在序列化时，将各结点的访问结果用'!'来分离。

二叉树的序列化过程如下：

当当前结点为空时，字符串中添加"#!"符号；
当当前结点不为空时，访问该结点，同时添加"!"符号；
递归访问左子树和右子树。

图片说明

在反序列化过程中，需要遍历所得到的字符串，具体步骤如下：

若字符串为空（即说明在序列化时得到的是空串），说明二叉树为空，直接返回 $NULL$ ；
若当前字符为'!'，说明是「结点与结点之间的分隔符」，因此直接对「全局」索引 $idx$ 加1，即向后移动一位；
若当前字符为'#'，说明该位置是一个空结点，因此直接返回 $NULL$ ，同时对 $idx$ 加1；
若当前字符是一个数字，则获取该数字，并构造出 $TreeNode$ 结点；
递归地完成构造左子树、右子树。

图片说明

基于上述思路，实现的代码如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    string s; // 定义全局变量s，存储字符串
    int idx = 0; // 定义全局变量idx，表示索引，在反序列化时用
    char* Serialize(TreeNode *root) {    
        serHelper(root); // 调用递归函数
        return (char *)s.data(); // 将返回值转为char*类型
    }
    void serHelper(TreeNode *root) {
        if (!root) { // 当前结点为空
            s += "#!"; 
            return; 
        }
        s += to_string(root->val) + "!"; // 访问当前结点，添加到s中
        serHelper(root->left); // 左子树
        serHelper(root->right); // 右子树
    }
    TreeNode* Deserialize(char *str) {
        s = str; // 构造全局变量s
        return desHelper(); // 调用递归函数
    }
    TreeNode* desHelper() {
        if (s.empty()) // 字符串为空
            return NULL; 
        if (s[idx] == '!') { // 当前字符为'!'
            idx++; 
            if (idx >= s.size()) // 到达末尾
                return NULL; 
        }
        if (s[idx] == '#') { // 当前字符为'#''
            idx++; 
            return NULL; 
        }
        int tmp = 0; // 用来表示整数
        while (s[idx] >= '0' && s[idx] <= '9') {
            tmp = tmp * 10 + (s[idx++] - '0'); 
        }
        TreeNode *root = new TreeNode(tmp); // 构造结点
        root->left = desHelper(); // 左子树
        root->right = desHelper(); // 右子树
        return root; 
    }
};

在序列化、反序列化时，分别需要遍历二叉树和字符串（且仅各遍历一次），因此时间复杂度为 $O(N)$ 级别；

在序列化、反序列化的递归过程中，都需要调用函数栈空间，因此空间复杂度为 $O(N)$ 级别。

解法二：层次遍历

二叉树的遍历同样可以利用「层次遍历」来实现。（二叉树层次遍历详见题解，本题与该题思路类似）

二叉树的序列化步骤如下（层次遍历）：

定义队列 $q$ ，首先将根结点入队列；
当不为空时，循环如下步骤：
1. 取 $q$ 的队头元素 $tmp$ ，若该元素不为 $NULL$ ，则将其拼到字符串中，同时 $tmp$ 也可能是一名父亲（当然也可能是叶结点），故需要将其左孩子、右孩子入队列；
2. 若队头元素为 $NULL$ ，直接在字符串中拼"#!"，且不需要将其孩子入队列（因为 $tmp$ 为空，其不可能是一名父亲）。

二叉树的反序列化同样需要借助队列实现，具体步骤如下：

为方便地访问字符串各位置的字符，需要将'!'先剔除，得到字符串 $tmp$ ；
定义队列 $q$ ，并将 $tmp$ 的第0个字符作为根结点入队列；
以下的操作均为”两两操作“，即：（在第0个位置元素已经入队列的前提下）先探讨 $tmp$ 的第1、2位置的元素情况，再探讨第3、4位置的元素情况，以此类推。其中，奇数位置为左孩子，偶数位置为右孩子。在每次探讨中，若结点不为'#'，说明是有效数字，则分别构造左/右孩子。

基于上述思路，实现的代码如下：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    string s; 
    char* Serialize(TreeNode *root) {    
        serHelper(root); // 调用递归函数
        return (char *)s.data(); // string转换为char*
    }
    void serHelper(TreeNode *root) {
        if (!root) { // 根结点为空
            s += "#!"; 
            return; 
        }
        queue<TreeNode *> q; 
        q.push(root); 
        while (q.size()) {
            TreeNode *tmp = q.front(); // 取队头元素
            q.pop(); 
            if (tmp) { // 队头结点不为空
                int num = tmp->val; 
                s += to_string(num) + "!"; // 添加到字符串中
                q.push(tmp->left); // 左孩子入队列
                q.push(tmp->right); // 右孩子入队列
            } else {
                s += "#!"; // 队头结点为空
            }
        }
    }
    TreeNode* Deserialize(char *str) {
        s = str; 
        TreeNode *root = desHelper(); // 调用递归函数
        return root; 
    }

    TreeNode* desHelper() {
        if (s.empty() || s[0] == '#') // 根结点为空
            return NULL; 
        vector<string> sVec; // 用来去掉'!'
        string tmp; 
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '!') // 当前字符不为'!'
                tmp += s[i]; 
            else { // 当前字符为'!'
                sVec.push_back(tmp); 
                tmp.clear(); 
            }
        }
        queue<TreeNode *> q; 
        TreeNode *root = new TreeNode(stoi(sVec[0])); // 根结点入队列
        q.push(root); 
        int idx = 1; 
        while (q.size()) { 
            TreeNode *p = q.front(); // 队头
            q.pop(); 
            if (idx < sVec.size() && sVec[idx] != "#") { // 查看当前结点左孩子情况
                p->left = new TreeNode(stoi(sVec[idx])); 
                q.push(p->left); // 左孩子入队列
            }
            idx++; // 向后移动
            if (idx < sVec.size() && sVec[idx] != "#") { // 查看当前结点右孩子情况
                p->right = new TreeNode(stoi(sVec[idx])); 
                q.push(p->right); // 右孩子入队列
            }
            idx++; // 向后移动
        }
        return root; 
    }
};

该方法在序列化、反序列化过程中仅需要遍历一次所有结点，故时间复杂度为 $O(N)$ ；

该方法在序列化、反序列化过程中均需要定义队列，故空间复杂度为 $O(N)$ 。

题解 | #序列化二叉树#

解法一：前序遍历

解法二：层次遍历