题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

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

提示： 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

---

算法

(DFS) $O(n)$

【1】序列化：前序遍历二叉树，对于空节点序列化为 #，对于非空节点将将值转换为字符串，每个节点之间用 , 隔开，为了反序列化判断节点边界。

【2】反序列化：根据一颗二叉树的前序序列中的非空节点和空节点可以反序列化出原二叉树。

1. 递归函数含义：TreeNode* d_dfs(string& s, int& u) $u$ 表示遍历到字符串 $s$ 的哪个位置了
2. 递归出口条件：当字符串的所有节点都处理完自动结束
3. 单层递归逻辑：
   • 如果当前字符是 $#$，则表示是空节点，直接返回空节点即可。
   • 否则是非空节点，找出非空节点的连续值（注意：可能是多位数，或者包括负号）
   • 创建当前节点，并递归创建它的左儿子和右儿子
   • 最后返回当前节点
     最后 deserialize() 中返回的就是二叉树的根节点

时间复杂度

$O(n)$，每个节点只会被遍历一次。

空间复杂度

$O(n)$，序列化后的字符串。

C++ 代码

​```cpp
/**
 * 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:
    string s;

    void s_dfs(TreeNode* root) {
        if (!root) {
            s += "#,";
            return;
        }

        s += to_string(root->val) + ',';
        s_dfs(root->left);
        s_dfs(root->right);
    }
    
    string serialize(TreeNode* root) {
        if (!root) return s;
        s_dfs(root);
        return s;
    }

    TreeNode* d_dfs(string& s, int& u) {
        if (s[u] == '#') {
            u += 2;
            return nullptr;
        }
        
        // 判断负号
        bool is_minus = false; 
        if (s[u] == '-') is_minus = true, u ++ ;
        int k = u;
        int val = 0;
        while (k < s.size() && s[k] != ',') val = val * 10 + (s[k ++ ] - '0');
        if (is_minus) val = -val;
        
        k ++ ;
        u = k;
        auto root = new TreeNode(val);
        root->left = d_dfs(s, u);
        root->right = d_dfs(s, u);
        return root;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        cout << data << endl;
        int u = 0;
        return d_dfs(data, u);
    }
};