本文涉及知识点

深度优先搜索 广度优先搜索
深度优先搜索汇总
图论知识汇总

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

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]

输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]

提示：
树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000

广度优先搜索

用深度优先搜索也可以，只是麻烦得多。
按树的层次存取，同层次年长的在前。为了不处理负数，保存时将数据加上1000。读取后，减去1000。

保存（序列化）

que记录待处理的节点。vector v记录各节点值对应的字符串，空节点对应空字符串。任意节点只有0个或1个父节点，所以无需visit数组，避免重复处理。
初始根节点入队，按顺序从que取节点，如果为空，则v追加空串。
否则：root的值转成字符串追加到v中。左右子节点入队。
v转成成字符串，中间用逗号隔开。

读取（反序列化)

如果字符串为空，返回null。
建立根节点，入队。
依次出队，读取数据。如果数据为空。忽略。
数据不为空，读取数据到节点，并为当前节点建立左右子节点，左右子节点入队。

代码

class Codec {
public:
	string serialize(TreeNode* root) {
		vector<string> v;
		queue<TreeNode*> que;
		que.emplace(root);
		while (que.size()) {
			auto cur = que.front();
			que.pop();
			if (nullptr == cur) { v.emplace_back(""); continue; }
			v.emplace_back(std::to_string(cur->val+1000));
			que.emplace(cur->left);
			que.emplace(cur->right);
		}
		string str;
		for (const auto& s : v) {
			str += s;
			str += ',';
		}
		str.pop_back();
		return str;
	}
	TreeNode* deserialize(string data) {
		if ("" == data) { return nullptr; }
		vector<int> nums;
		for (int left = 0, r = 0; left < data.length(); left = r) {
			int num = 0;
			while ((r < data.length()) && (',' != data[r])) {
				num = num * 10 + data[r] - '0';
				r++;
			}
			if (left == r) {
				nums.emplace_back(INT_MIN);
			}
			else {
				nums.emplace_back(num-1000);
			}
			r++;
		}
		if (',' == data.back()) {
			nums.emplace_back(INT_MIN);
		}
		TreeNode* root = new TreeNode(nums[0]);
		vector< TreeNode*> nodes;
		nodes.emplace_back(root);
		for (int i = 1; i < nums.size(); i++) {
			if (INT_MIN == nums[i]) {
				continue;
			}
			TreeNode* cur = new TreeNode(nums[i]);
			nodes.emplace_back(cur);
			const int inx = (i - 1) / 2;
			if (1 & i) {
				nodes[inx]->left = cur;
			}
			else {
				nodes[inx]->right = cur;
			}
		}
		return root;
	}
};

2023年6月版，就是用的深度优先

也不是很麻烦。前序遍历，用括号括起来一个子树，可读性似乎好些。

class Codec {
public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		auto str = serializeInner(root);
		//std::cout << str << std::endl;
		return str;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		int iPos = 0;
		return deserialize(data, iPos);
	}
private:
	string serializeInner(TreeNode* root) {
		if (nullptr == root)
		{
			return "()";
		}
		return "(" + std::to_string(root->val) + serialize(root->left) + serialize(root->right) + ")";
	}

	TreeNode* deserialize(string data,int& iPos) 
	{
		if (iPos >= data.length())
		{
			return nullptr;
		}
		iPos++;
		if ( ')' == data[iPos])
		{
			iPos ++;
			return nullptr;
		}
		int iValue = 0;
		int iSign = 1;
		if ('-' == data[iPos])
		{
			iSign = -1;
			iPos++;
		}
		while (::isdigit(data[iPos]))
		{
			iValue = iValue * 10 + data[iPos] - '0';
			iPos++;
		}
		iValue *= iSign;
		TreeNode* p = new TreeNode(iValue);
		p->left = deserialize(data, iPos);
		p->right = deserialize(data, iPos);
		iPos++;
		return p;
	}
};