LeetCode-树-层序遍历(BFS)-二叉树的序列化与反序列化

LeetCode-树-层序遍历(BFS)-二叉树的序列化与反序列化 1 二叉树的序列化

        序列化参考：请问 [1, null, 2, 3] 在二叉树测试用例中代表什么 - 力扣（LeetCode） - 支持

2 题目

剑指 Offer II 048. 序列化与反序列化二叉树

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

2.1 序列化         

        null的作用就是避免歧义，也就是起到占位符的作用，这样能够明确到底是其父节点的左孩子，还是右孩子。

        当前层如果不是最后一层，最后一个非NULL元素(比如上图中的3)后面的null也要打印出来，因为这样才能标识出来3是其父节点2的左子节点；但是如果当前层是最后一层，最后一个非NULL元素(比如上图中的4)的null则不用打印出来。

        当前层的第一个非NULL元素前面的NULL元素如何处理？

        如果第一个非NULL元素的前面的NULL的父节点是非NULL节点，则这样的NULL元素就需要打印出来，比如2前面的NULL元素的父节点是1,1是一个非NULL节点，所以就需要输出null；

        下一层的元素3，前面 也有NULL节点，但是他们的父节点是NULL节点，此时就不需要输出null。

        判断是否是最后一层的标志就是：该层的子节点全部是NULL节点。

2.2 反序列化

        需要先保存父节点，然后让父节点指向后续的子节点。

2.3 实现

class Codec {
public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		string res;
		res.append(1, '[');
		do
		{
			if (!root)
				break;			

			queue q;
			q.push(root);

			int lastNonNullIndex = 1, step = 0;
			//lastNonNullIndex为0说明上一层是最后一层
			while (lastNonNullIndex)
			{
				queue q2;
				lastNonNullIndex = 0;
				int validLevelSize = 0;
				
				while (!q.empty())
				{
					TreeNode* tmp = q.front();
					q.pop();
					if (step)
					{
						if (tmp)
						{
							res.append(1, ',').append(to_string(tmp->val));
						}
						else
						{
							res.append(1, ',').append("null");
						}
					}
					else
					{
						if (tmp)
						{
							res.append(to_string(tmp->val));
						}
						else
						{
							res.append("null");
						}
					}

                    //非NULL节点的子节点(包含NULL子节点)才能入队
					if (tmp)
					{
						q2.push(tmp->left);
						++validLevelSize;
						if (tmp->left)
							lastNonNullIndex = validLevelSize;

						q2.push(tmp->right);
						++validLevelSize;
						if (tmp->right)
							lastNonNullIndex = validLevelSize;
					}
				}

				++step;
				q.swap(q2);
			}			
		} while (0);

        //删除最后一层的额外的尾部null
		while (res.length() > 4 && res.substr(res.length() - 4) == string("null"))
		{
			res.resize(res.length() - 5);
		}
		res.append(1, ']');
		return res;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		if (data.empty())
			return NULL;

		TreeNode* root = NULL, *tmp = NULL, *parent = NULL;
		size_t pos = -1, lastPos = 1;
		string str;
		queue q;
		while ((pos = data.find(',', lastPos)) != string::npos)
		{
			str = data.substr(lastPos, pos - lastPos);
			lastPos = pos + 1;

			if (str.compare("null") == 0)
			{
				tmp = NULL;
			}
			else
			{
				tmp = new TreeNode(std::stoi(str));
			}

			q.push(tmp);
		}

		str = data.substr(lastPos, data.length() - 1 - lastPos);
		if (!str.empty())
		{
			tmp = new TreeNode(std::stoi(str));
			q.push(tmp);
		}

		queue q2;
		while (!q.empty())
		{
            tmp = q.front();
            q.pop();
            if (!root)
            {
                root = tmp;
            }

            if (!parent)
            {
                if (!q2.empty())
                {
                    parent = q2.front();
                    q2.pop();
                    parent->left = tmp;
                }
            }
            else
            {
                parent->right = tmp;
                parent = NULL;
            }

            //q2中保存的是用作父节点的节点,null节点不能作为父节点，所以不需要放入q2中
            if (tmp)
            {
                q2.push(tmp);
            }
		}

		return root;
	}
};

2.4