[剑指-Offer] 37. 序列化二叉树(层序遍历、前序遍历、递归、特殊情况)

1. 题目来源

链接：序列化二叉树
来源：LeetCode——《剑指-Offer》专项

2. 题目说明

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

示例：

你可以将以下二叉树：

     1    / \  2   3/ \4   5

序列化为 “[1,2,3,null,null,4,5]”

3. 题目解析

方法一：层序遍历+迭代解法

这是一道 Hard 题，思路还是很清楚的，难就难在了字符串处理以及最后的测试用例 47、48 的数据接收上了。

• 使用层序遍历序列化二叉树。层次遍历是不能唯一确定一颗二叉树的。 若遇到一个节点空节点用 '#' 表示。每个节点后面添加一个 ',' 代表结束，则可以唯一确定一颗二叉树。
• 上述二叉树层次序列化得到 1,2,3,#,#,4,5,#,#,#,#,
• 然后根据该序列反序列化。 （注意判断负数的情况）

说说我遇到的坑点吧：

• 首先在序列化的时候，不能直接采用 string 的 push_back 方法，实在是过不去测试用例 47、48，可以采用 += 字符串的形式，也可以采用字符流的形式
• 不能仅仅采用一种标记层次序列化的方式，即不能仅添加 # 来分割字符串，这样做没办法唯一确定一颗二叉树，当树的节点值 val 大于 10 时，将没有办法直接正常的取出 val 值，因为 #12# 产生歧义，不知道到底是 1、2 还是 12
• 节点值为负数的情况需要处理，这个确实一开始给忽略掉了
• 最末尾的 # 需要去掉，这个很容易想得到

基本上大点的坑点都在上面提示到了，果然 Hard 就不一般…一道简单的 dfs、bfs 硬是把我整的没脾气…

不好的解法1

思路太年轻，写的很爽，过不了…在这里是将整形 val 转为了 char 类型，所以在 string 取的话按位取也能直接取出来。

参见代码如下：

// 没 AC，样例 47/48 过不去
// [1,null,2,null,3,null,4,null,5,null,6,null,...,999,null,1000] 单支树，IO极其密集class Codec {
public:// Encodes a tree to a single string.string serialize(TreeNode* root) {string s;queue<TreeNode*> q;if (root) q.push(root);while (!q.empty()) {TreeNode *t = q.front(); q.pop();if (t) {s.push_back(t->val);	// 过不去，string 爆掉了q.push(t->left);q.push(t->right);} else {s.push_back('#');}}return s;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {int cnt = data.find_last_not_of('#');if (cnt != std::string::npos)data.erase(cnt + 1);elsedata.clear();   if (data.empty()) return nullptr;queue<TreeNode*> q;string val(data);TreeNode *res = new TreeNode(val[0]), *cur = res;q.push(cur);int i = 1;while (!q.empty()) {TreeNode *t = q.front(); q.pop();if (i > val.size() - 1) break;if (val[i] != '#') {cur = new TreeNode(val[i]);q.push(cur);t->left = cur;++i;}else {++i;}if (i > val.size() - 1) break;if (val[i] != '#') {cur = new TreeNode(val[i]);q.push(cur);t->right = cur;++i;}else {++i;}}return res;}
};

不好的解法2

改成字符串流进行操作，能够正常读取测试用例 47 了，这样按字符读入，就将整数 123 拆成了 1 2 3，这三个字符，在后续 string [ ] 操作就不能输出完整的整数，也是报错了。即便对字符串进行处理，但由于字符串中仅添加 # 来分割字符串，没办法唯一确定一颗二叉树，当树的节点值 val 大于 10 时，将没有办法直接正常的取出 val 值，因为 #12# 产生歧义，不知道到底是 1、2 还是 12，所以需要考虑唯一确定一颗二叉树！

class Codec {
public:// Encodes a tree to a single string.string serialize(TreeNode* root) {queue<TreeNode*> q;q.push(root);stringstream ss;while (!q.empty()) {root = q.front();q.pop();if (root) {q.push(root->left);q.push(root->right);ss << root->val;}else {ss << '#';}}string data = ss.str();return data;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {int cnt = data.find_last_not_of('#');if (cnt != std::string::npos)data.erase(cnt + 1);elsedata.clear();   if (data.empty()) return nullptr;queue<TreeNode*> q;string val(data);TreeNode *res = new TreeNode(val[0] -'0'), *cur = res;q.push(cur);int i = 1;while (!q.empty()) {TreeNode *t = q.front(); q.pop();if (i > val.size() - 1) break;if (val[i] != '#' && i < val.size() - 1) {string tmp;while (i < val.size() && val[i] != '#' ) {tmp += val[i];++i;}cur = new TreeNode(stoi(tmp));q.push(cur);t->left = cur;}else {++i;}if (i > val.size() - 1) break;if (val[i] != '#') {string tmp;while (i < val.size() && val[i] != '#') {tmp += val[i];++i;}cur = new TreeNode(stoi(tmp));q.push(cur);t->right = cur;}else {++i;}}return res;}
};

成功版

解决掉上述问题，再解决负数问题，这题就搞定了！

参见代码如下：

// 执行用时 :8 ms, 在所有 C++ 提交中击败了84.14%的用户
// 内存消耗 :10 MB, 在所有 C++ 提交中击败了100.00%的用户/*** 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 {
private:string encode(TreeNode* root) {if (!root) return "#,";string res = "";queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode *t = q.front(); q.pop();if (t) {res += to_string(t->val) + ",";q.push(t->left);q.push(t->right);} else {res += "#,";}}return res;}TreeNode* takeNum(const string& data, int& p) {if (data[p] == '#') {p += 2;return NULL;}bool isN = false;if (data[p] == '-') {isN = true;p++;}int val = 0;while (data[p] != ',') {val = val * 10 + (data[p] - '0');p++;}p++;if (isN) {val = -val;}return new TreeNode(val);}TreeNode* decode(const string& data) {if (data[0] == '#') return NULL;int p = 0;TreeNode *root = takeNum(data, p);queue<TreeNode*> q;q.push(root);while (!q.empty()) {TreeNode *t = q.front(); q.pop();TreeNode *l = takeNum(data, p);TreeNode *r = takeNum(data, p);if (l) q.push(l);if (r) q.push(r);t->left = l;t->right = r;}return root;}public:// Encodes a tree to a single string.string serialize(TreeNode* root) {string s = encode(root);return s;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {TreeNode *root = decode(data);return root;}
};// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

方法二：先序遍历+递归解法

借助输入和输出字符串流 istringstream 和 ostringstream。

• 对于序列化，从根节点开始，如果节点存在，则将值存入输出字符串流，然后分别对其左右子节点递归调用序列化函数即可。
• 对于去序列化，先读入第一个字符，以此生成一个根节点，然后再对根节点的左右子节点递归调用去序列化函数即可
• 还是各种细节问题的处理，和上面差不多，就不在赘述，但是递归明显简洁许多

参见代码如下：

// 执行用时 :40 ms, 在所有 C++ 提交中击败了63.53%的用户
// 内存消耗 :26.5 MB, 在所有 C++ 提交中击败了100.00%的用户/*** 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:// Encodes a tree to a single string.string serialize(TreeNode* root) {ostringstream out;serialize(root, out);return out.str();}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {istringstream in(data);return deserialize(in);}
private:void serialize(TreeNode *root, ostringstream &out) {if (root) {out << root->val << ' ';serialize(root->left, out);serialize(root->right, out);} else {out << "# ";}}TreeNode* deserialize(istringstream &in) {string val;in >> val;if (val == "#") return nullptr;TreeNode *root = new TreeNode(stoi(val));root->left = deserialize(in);root->right = deserialize(in);return root;}
};// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));