题目描述
您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。
数据范围
树中节点数量 [0,1000]。
样例
你可以序列化如下的二叉树 8 / \ 12 2 / \ 6 4 为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"
注意:
- 以上的格式是AcWing序列化二叉树的方式，你不必一定按照此格式，所以可以设计出一些新的构造方式。
方法一：dfs O(n)
我们可以通过前序遍历来序列化和反序列化。
序列化：
- 如果当前遍历的结点为空，则往
res后加'#'。 - 如果当前遍历的结点不为空，则将当前结点的值转换成字符串加到
res后面，同样也要加空格。 - 分别遍历结点的左右子树，进行上述相同操作。
反序列化：
如果此时已经遍历到 data 的最后，则结束遍历。
获取 data 的第一串字符。
如果第一串字符为 # ，则说明该结点为空，直接返回 NULL 即可。
如果第一串字符为数字，则需要判断是正数还是负数，然后将字符串转换成数字。
创建该结点，把上面得到的值赋给它。
继续往后遍历生成该结点的左右孩子。
/** * 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 res = ""; dfs_s(root, res); return res; } void dfs_s(TreeNode* root, string& res) { if (!root) { res += "# "; //空结点用#来表示 return; } //利用前序遍历来生成字符串 res += to_string(root->val) + ' '; //同样在后面要加一个空格方便反序列化判断 dfs_s(root->left, res); dfs_s(root->right, res); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { int u = 0; return dfs_d(data, u); } TreeNode* dfs_d(string data, int& u) { if (u == data.size()) return NULL; int k = u; while (data[k] != ' ') k++; //先截取出序列中的一串字符 //如果是井号说明是空结点，则直接返回 if (data[u] == '#') { u = k + 1; //找到下一串字符的首部 return NULL; } //判断数字的正负号 int num = 0; if (data[u] == '-') { for (int i = u + 1; i < k; i++) num = num * 10 + data[i] - '0'; num *= -1; } else { for (int i = u; i < k; i++) num = num * 10 + data[i] - '0'; } u = k + 1; //找到下一串字符的首部 TreeNode* root = new TreeNode(num); //创建结点 root->left = dfs_d(data, u); root->right = dfs_d(data, u); return root; } };
欢迎大家在评论区交流~
