0%

二叉树的序列化与反序列化

发表于 分类于 ， Disqus：

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

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

1
2
3
4
5
  1
 / \
2   3
   / \
  4   5

得到 “[1,2,3,null,null,4,5]”。

小贴士: 不要使用类的成员/全局/静态变量来存储状态机，你的序列化和反序列化算法应该是无状态的。

解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
	int m = depth(root);
	vector<vector<string>> collection(m, vector<string>());
	serializeRecur(root, collection, m, 0);
	string res = "[";
	for (auto i = collection.begin(); i != collection.end(); i++) {
		for (auto j = i->begin(); j != i->end(); j++) {
			if (i == collection.end() - 1 && j == i->end() - 1) {
				res += *j;
			}
			else {
				res += *j + ",";
			}
		}
	}
	res += "]";
	return res;
}


// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
	vector<string> items = explode(data, ",");
	map<size_t, vector<TreeNode*>> collection;
	if (items.size() == 0) return NULL;
	collapse(items, collection, 0, 0);
	for (size_t i = 0; i < collection.size() - 1; i++) {
		size_t step = 0;
		for (size_t j = 0; j < collection[i].size(); j++) {
			auto item = collection[i][j];
			size_t next = step * 2;
			if (!item) continue;
			if (next >= collection[i + 1].size()) break;
			item->left = collection[i + 1][next];
			if (next + 1 >= collection[i + 1].size()) break;
			item->right = collection[i + 1][next + 1];
			step++;
		}
	}
	TreeNode* root = collection[0][0];
	return root;
}


void collapse(vector<string>& items, map<size_t, vector<TreeNode*>>& collection, size_t pos, size_t depth, size_t len = 1) {
	if (pos >= items.size()) {
		return;
	}
	size_t step = 0;
	for (size_t i = 0; i < len; i++) {
		if (pos >= items.size()) {
			break;
		}
		auto item = convert2Node(items[pos++]);
		collection[depth].push_back(item);
		if (item != NULL) {
			step++;
		}
	}
	collapse(items, collection, pos, depth + 1, step * 2);
}


void serializeRecur(TreeNode* root, vector<vector<string>>& collection, int m, size_t depth) {
	if (!root) {
		if (depth < (size_t)m) {
			collection[depth].push_back("null");
		}
		return;
	}
	collection[depth].push_back(to_string(root->val));
	serializeRecur(root->left, collection, m, depth + 1);
	serializeRecur(root->right, collection, m, depth + 1);
}

TreeNode* convert2Node(string str) {
	if (str == "null") {
		return NULL;
	}
	TreeNode* node = new TreeNode(stoi(str));
	return node;
}

vector<string> explode(string str, string seperator) {
	regex re(R"#([\[\]]|\s+)#");
	str = regex_replace(str, re, "");
	vector<string> res;
	if (str.size() == 0) {
		return res;
	}
	size_t start = 0;
	bool flag = true;
	while (flag) {
		size_t pos = str.find(seperator, start);
		if (pos != string::npos) {
			res.push_back(str.substr(start, pos - start));
			start = pos + 1;
		}
		else {
			res.push_back(str.substr(start));
			flag = false;
		}
	}
	return res;
}

int depth(TreeNode* root) {
	if (root == NULL) return 0;
	if (root->left == NULL && root->right == NULL) return 1;
	return max(depth(root->left), depth(root->right)) + 1;
}

他山之石其一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		string val;
		if (root == NULL)
			val = "# ";
		else
		{
			val = to_string(root->val) + string(" ");
			val = val + serialize(root->left) + serialize(root->right);
		}
		return val;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		stringstream iss;
		iss.str(data);
		TreeNode* node = decode(iss);
		return node;
	}

	TreeNode* decode(stringstream &in) {
		string val;
		in >> val;
		if (val == "#") return nullptr;
		TreeNode *root = new TreeNode(stoi(val));
		root->left = decode(in);
		root->right = decode(in);
		return root;
	}

他山之石其二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
	}