# 问题 原题链接：[https://leetcode.com/problems/serialize-and-deserialize-binary-tree/](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/) Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. Example: ``` You may serialize the following tree: 1 / \ 2 3 / \ 4 5 as "[1,2,3,null,null,4,5]" ``` Clarification: - The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself. Note: - Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless. # 分析过程 - 输入：一棵二叉树 或 一段序列化数据结构 - 输出：一段序列化数据结构 或 一棵二叉树 - 思路： - 归档可以使用树的深度遍历和广度遍历，我使用了深度遍历。 - 归档的关键是要把空节点也输出，否则解档递归不知道何时应该返回。 - 解档的返回条件是找到了空节点，非法节点可以截断或者直接 fatal。 # 解决方法 ```cpp class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { if (!root) { return "null"; } vector<string> vec; _serialize(root, vec); string result = vec[0]; for (int i = 1; i < vec.size(); i++) { result += "," + vec[i]; } return result; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if (data == "" || data == "nullptr") { return nullptr; } vector<string> vec; istringstream stream(data); string tmp; while (getline(stream, tmp, ',')) { vec.push_back(tmp); } int i = 0; return _deserialize(vec, &i); } private: void _serialize(TreeNode *root, vector<string>& vec) { char buf[5]; // 把节点的值输出 sprintf(buf, "%d", root->val); vec.push_back(string(buf)); // 递归输出左右子树，如果是空的则输出 null root->left ? _serialize(root->left, vec) : vec.push_back("null"); root->right ? _serialize(root->right, vec) : vec.push_back("null");; } TreeNode *_deserialize(vector<string>& vec, int *index) { TreeNode *node = _deserializeNode(vec.at(*index)); ++*index; if (!node) { return nullptr; } // 递归解档左右子树 node->left = _deserialize(vec, index); node->right = _deserialize(vec, index); return node; } static TreeNode *_deserializeNode(string& str) { if (str == "null") { return nullptr; } else { int v; if (sscanf(str.c_str(), "%d", &v) != 1) { // 不是 null，也不是合法的数字 // 可以 fatal，也可以忽略直接截断 return nullptr; } return new TreeNode(v); } } }; ```