【深度优先搜索广度优先搜索】297. 二叉树的序列化与反序列化

码农世界 2024-06-13 后端 84 次浏览 0个评论

本文涉及知识点

深度优先搜索广度优先搜索

深度优先搜索汇总

图论知识汇总

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 v;
		queue 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 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;
	}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛