一、什么是序列化与反序列化在计算机中很多数据结构都是存在于内存里的比如链表、二叉树、图等。这些结构在程序运行时很好使用但如果我们想把它们保存到文件中存入数据库通过网络发送给另一台电脑程序退出后下次还能恢复就不能直接保存内存中的指针关系。这时就需要用到序列化和反序列化。二、序列化的概念序列化就是把一个对象或数据结构转换成一种可以存储、传输的格式。比如一棵二叉树1 / \ 2 3 / \ 4 5它在内存中是由很多节点和指针连接起来的。但是指针地址不能直接保存因为程序重新运行后内存地址会改变。所以我们需要把这棵树转换成字符串例如1,2,#,#,3,4,#,#,5,#,#这个字符串就可以保存到文件中也可以通过网络传输。这个过程就叫做序列化。三、反序列化的概念反序列化就是把序列化后的字符串重新还原成原来的数据结构。例如我们拿到字符串1,2,#,#,3,4,#,#,5,#,#可以重新构造出原来的二叉树1 / \ 2 3 / \ 4 5这个过程就叫做反序列化。四、为什么二叉树需要序列化普通数组的序列化很简单例如[1, 2, 3, 4, 5]可以直接转换成1,2,3,4,5但是二叉树比较特殊。二叉树不仅有节点值还有结构关系1 / 2和1 \ 2这两棵树的节点值都是1和2但结构完全不同。所以序列化二叉树时不能只保存节点值还必须保存空节点的位置。五、为什么要记录空节点假设我们只用前序遍历保存节点值。下面这棵树1 / 2前序遍历结果是1,2而下面这棵树1 \ 2前序遍历结果也是1,2这样就无法判断2是1的左孩子还是右孩子。所以我们需要用一个特殊符号表示空节点例如#。第一棵树可以序列化成1,2,#,#,#第二棵树可以序列化成1,#,2,#,#这样结构就明确了。六、题目分析LeetCode 297题目要求给定一棵二叉树要求我们设计两个函数string serialize(TreeNode* root); TreeNode* deserialize(string data);其中serialize把二叉树转换成字符串deserialize把字符串重新还原成二叉树题目不要求必须使用 LeetCode 官方格式只要能够保证deserialize(serialize(root))可以还原原来的树结构即可。七、解决思路前序遍历 空节点标记二叉树常见的遍历方式有前序遍历根 左 右中序遍历左 根 右后序遍历左 右 根层序遍历按层遍历这道题可以用很多方式实现。这里我们使用最经典的一种方法前序遍历 空节点标记1. 序列化过程按照前序遍历的顺序根节点 - 左子树 - 右子树如果当前节点为空就记录#。例如二叉树1 / \ 2 3 / \ 4 5前序序列化过程如下1 2 # # 3 4 # # 5 # #最终得到字符串1,2,#,#,3,4,#,#,5,#,#2. 反序列化过程反序列化时也按照前序顺序读取字符串。遇到数字就创建节点。遇到#说明当前位置是空节点返回nullptr。例如字符串1,2,#,#,3,4,#,#,5,#,#解析过程如下1 作为根节点 2 作为 1 的左孩子 # 表示 2 的左孩子为空 # 表示 2 的右孩子为空 3 作为 1 的右孩子 4 作为 3 的左孩子 # 表示 4 的左孩子为空 # 表示 4 的右孩子为空 5 作为 3 的右孩子 # 表示 5 的左孩子为空 # 表示 5 的右孩子为空这样就能完整还原原来的二叉树。八、C 完整代码#include iostream #include sstream #include string using namespace std; // LeetCode 中已经定义好了 TreeNode这里写出来方便理解 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class Codec { public: // 序列化将二叉树转换成字符串 string serialize(TreeNode* root) { string result; dfsSerialize(root, result); return result; } // 反序列化将字符串重新转换成二叉树 TreeNode* deserialize(string data) { stringstream ss(data); return dfsDeserialize(ss); } private: // 前序遍历序列化 void dfsSerialize(TreeNode* root, string result) { if (root nullptr) { result #,; return; } // 先保存当前节点 result to_string(root-val) ,; // 再保存左子树 dfsSerialize(root-left, result); // 最后保存右子树 dfsSerialize(root-right, result); } // 前序遍历反序列化 TreeNode* dfsDeserialize(stringstream ss) { string token; getline(ss, token, ,); // 如果是空节点标记返回 nullptr if (token #) { return nullptr; } // 创建当前节点 TreeNode* root new TreeNode(stoi(token)); // 递归构造左子树 root-left dfsDeserialize(ss); // 递归构造右子树 root-right dfsDeserialize(ss); return root; } };九、代码详细解释1. serialize 函数string serialize(TreeNode* root) { string result; dfsSerialize(root, result); return result; }这个函数负责把二叉树转换成字符串。真正的递归逻辑在dfsSerialize中完成。2. dfsSerialize 函数void dfsSerialize(TreeNode* root, string result) { if (root nullptr) { result #,; return; } result to_string(root-val) ,; dfsSerialize(root-left, result); dfsSerialize(root-right, result); }这个函数使用前序遍历根节点 - 左子树 - 右子树如果当前节点为空就加入#,如果当前节点不为空就加入节点值。例如节点值是3就加入3,3. deserialize 函数TreeNode* deserialize(string data) { stringstream ss(data); return dfsDeserialize(ss); }这个函数把字符串放入stringstream中方便我们按照逗号逐个读取。例如字符串1,2,#,#,3,#,#,每次读取一个片段1 2 # # 3 # #4. dfsDeserialize 函数TreeNode* dfsDeserialize(stringstream ss) { string token; getline(ss, token, ,); if (token #) { return nullptr; } TreeNode* root new TreeNode(stoi(token)); root-left dfsDeserialize(ss); root-right dfsDeserialize(ss); return root; }这个函数的核心思想是读取一个字符串片段如果是#说明当前位置为空如果是数字创建一个新节点递归构建它的左子树和右子树因为序列化时使用的是前序遍历所以反序列化时也必须按照前序顺序还原。十、示例演示输入二叉树root [1,2,3,null,null,4,5]对应结构1 / \ 2 3 / \ 4 5序列化结果1,2,#,#,3,4,#,#,5,#,#,反序列化后重新得到1 / \ 2 3 / \ 4 5十一、为什么这种方法一定能还原原树关键在于我们记录了空节点。前序遍历本身只能确定访问顺序但不能唯一确定树的结构。加入空节点标记后每个节点的左右孩子信息都被完整保存了。例如1,2,#,#,3,#,#表示1 / \ 2 3而1,2,#,3,#,#,#表示1 / 2 \ 3虽然节点值相似但因为空节点的位置不同所以可以还原出不同的结构。这就是空节点标记的作用。十二、复杂度分析假设二叉树中有n个节点。时间复杂度序列化时每个节点访问一次。反序列化时每个节点也只创建一次。所以时间复杂度为O(n)空间复杂度序列化字符串需要保存所有节点和空节点。递归调用栈在最坏情况下也就是树退化成链表时需要O(n)的空间。所以空间复杂度为O(n)十三、层序遍历能不能做当然可以。LeetCode 官方显示二叉树时常用的是层序遍历格式[1,2,3,null,null,4,5]也可以用 BFS 层序遍历来序列化。例如1 / \ 2 3 / \ 4 5层序序列化结果可以是1,2,3,#,#,4,5,#,#,#,#不过层序遍历实现时需要用队列而且要处理末尾多余的空节点。相比之下前序遍历写法更简洁逻辑也更适合递归理解。十四、常见错误总结1. 没有记录空节点错误写法1,2,3,4,5这种只记录节点值无法恢复树的结构。二叉树序列化必须保存空节点信息。2. 序列化和反序列化顺序不一致如果序列化使用前序遍历根 左 右反序列化也必须按照前序顺序解析。不能序列化时用前序反序列化时却按照层序处理。3. 忘记处理负数题目中说明-1000 Node.val 1000所以节点值可能是负数。使用stoi(token)可以正常处理负数。4. 忘记处理空树如果根节点为空root []序列化结果可以是#,反序列化时读取到#直接返回nullptr。十五、总结二叉树的序列化与反序列化本质上是把内存中的树结构转换成字符串再从字符串恢复成原来的树结构。这道题的核心不是遍历本身而是如何完整保存树的结构信息。最重要的一点是序列化二叉树时必须记录空节点。本文使用的方案是前序遍历 空节点标记优点是思路清晰代码简洁容易实现可以唯一还原二叉树结构对于 LeetCode 297 这道题来说这是一种非常经典且高效的解法。十六、核心记忆可以把这道题记成一句话序列化就是把树变成字符串反序列化就是把字符串还原成树为了保证能还原结构必须把空节点也记录下来。