Tag Archives: 序列化

LeetCode Serialize and Deserialize BST

LeetCode Serialize and Deserialize BST Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure. The encoded string should be as compact as possible. Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.


本题要序列化和反序列化二叉搜索树。因为二叉搜索树属于二叉树,所以可以直接用LeetCode Serialize and Deserialize Binary Tree对普通二叉树的序列化和反序列化方法。但是二叉搜索树又有其特殊性,即左孩子小于等于根节点,根节点小于等于右孩子。所以如果知道树中有哪些数,通过插入的方法就可以构造好二叉搜索树。 首先还是根据层次遍历或者树的先序遍历得到树的序列化表示,那么序列化的第一个数就是根节点了。反序列化时,依次插入后续的节点构成一棵二叉搜索树就好了。但是数值插入的顺序不能乱,比如下图,虽然确定了根节点是1,如果先插入了4号节点,再插入3号节点,则反序列化得到的树就不是原来的树了。为了保证序列化到的数值顺序正确,可以使用层次遍历或者树的先序遍历。 完整代码如下: [cpp] class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { if (root == NULL)return ""; string ans = to_string(root->val); if (root->left) ans += ","+serialize(root->left); if (root->right) ans += ","+serialize(root->right); return ans; } void insert(TreeNode* root, TreeNode* node) { if (node->val < root->val) { if (root->left == NULL)root->left = node; else insert(root->left, node); } else { if (root->right == NULL)root->right = node; else insert(root->right, node); } } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if (data == "")return NULL; TreeNode* root = NULL; for (int start = 0, end = 0; end <= data.size(); ++end) { if (data[end] == ‘,’ || end == data.size()) { TreeNode* node = new TreeNode(atoi(data.substr(start, end – start).c_str())); if (root == NULL)root = node; else insert(root, node); start = end + 1; } } return root; } }; [/cpp] 本代码提交AC,用时26MS。]]>

LeetCode Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.


序列化一棵二叉树。要求把一棵二叉树转换为一个字符串,并且能根据这个字符串反序列化回原来的二叉树。
首先我们使用LeetCode Binary Tree Level Order Traversal层次遍历的方法得到二叉树的层次遍历序列,然后把数字转换为字符串并用逗号拼接起所有字符串,遇到空节点,则用空字符串表示。比如下面这棵树,序列化成字符串为:1,2,3,,,4,,,5。本来5后面还有空串的,即3的右孩子及其孩子,但是为了节省空间,后面的空串和逗号都省略了。

反序列化有点技巧。正常如果是一棵完全二叉树,如果下标从0开始,则节点i的左右孩子的下标分别为2*i+1和2*i+2,所以我们可以用递归的方法快速反序列化出来,就像我在LeetCode Minimum Depth of Binary Tree给出的根据数组构建树结构的genTree函数一样。对应到上图,完全二叉树的数组表示应该是{1,2,3,-1,-1,4,-1,-1,-1,-1,-1,-1,5,-1,-1},只有把这个数组传入genTree函数才能生成像上图的二叉树。
因为经过层次遍历之后的数组是{1,2,3,-1,-1,4,-1,-1,5},也就是说2后面只保留了其直接的两个空节点,并没有保留其4个空的孙子节点。导致4号节点(下标为5)在找孩子节点时,使用2*i+1=11和2*i+2=12找左右孩子的下标时,数组越界,导致漏掉了右孩子5。
后来参考了LeetCode官方的二叉树反序列化作者的介绍,恍然大悟。因为数组是层次遍历的结果,所以兄弟节点的孩子节点是按先后顺序存储在数组中的,我们可以分别维护一个父亲节点par和孩子节点child,一开始par=0,child=1,表示数组的0号节点为父亲节点,1号节点为左孩子节点,然后我们把child接到par的左孩子,把child+1接到par的右孩子,par++,child+=2,当遇到child为空,也要把空节点接到par上面。当遇到par为空时,直接跳过就好,但是child不移动。这样就能避免父亲为空,孩子节点的下标对不上的问题。比如上例中,par指向数值3时,左child指向数值4,右child指向-1;当par指向后面的两个-1时,child不动;当par指向4时,左child指向下一个-1,右child指向5正确。
完整代码如下:

class Codec {
public:
    string bfs(TreeNode* root)
    {
        if (root == NULL)
            return "";
        string tree = "";
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* t = q.front();
            q.pop();
            if (t == NULL) {
                tree += ",";
                continue;
            }
            tree += to_string(t->val) + ",";
            q.push(t->left);
            q.push(t->right);
        }
        return tree;
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root)
    {
        string tree = bfs(root);
        if (tree == "")
            return "";
        int end = tree.size() – 1;
        while (tree[end] == ‘,’)
            –end;
        return tree.substr(0, end + 1);
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data)
    {
        if (data == "")
            return NULL;
        vector<TreeNode*> tree;
        for (int start = 0, end = 0; end <= data.size(); ++end) {
            if (data[end] == ‘,’ || end == data.size()) {
                string tmp = data.substr(start, end – start);
                if (tmp == "")
                    tree.push_back(NULL);
                else
                    tree.push_back(new TreeNode(atoi(tmp.c_str())));
                start = end + 1;
            }
        }
        int par = 0, child = 1;
        while (child < tree.size()) {
            if (tree[par]) {
                if (child < tree.size())
                    tree[par]->left = tree[child++];
                if (child < tree.size())
                    tree[par]->right = tree[child++];
            }
            ++par;
        }
        return tree[0];
    }
};

本代码提交AC,用时39MS。

二刷。逻辑性更好的代码:

class Codec {
public:

	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		vector<string> nodes;
		queue<TreeNode*> q;
		q.push(root);
		while (!q.empty()) {
			int n = q.size();
			while (n--) {
				TreeNode* cur = q.front();
				q.pop();
				if (cur == NULL)nodes.push_back("null");
				else {
					nodes.push_back(to_string(cur->val));
					q.push(cur->left);
					q.push(cur->right);
				}
			}
		}
		string ans = "";
		int n = nodes.size();
		for (int i = 0; i < n - 1; ++i) {
			ans += nodes[i] + ",";
		}
		return ans + nodes[n - 1];
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		vector<string> nodes;
		int n = data.size();
		int i = 0, j = 0;
		while (i < n) {
			j = i + 1;
			while (j < n&&data[j] != ',')++j;
			string cur = data.substr(i, j - i);
			nodes.push_back(cur);
			i = j + 1;
		}

		vector<TreeNode*> tnodes;
		for (int i = 0; i < nodes.size(); ++i) {
			if (nodes[i] == "null")tnodes.push_back(NULL);
			else tnodes.push_back(new TreeNode(atoi(nodes[i].c_str())));
		}
		
		int par = 0, child = 1;
		while (child < tnodes.size()) {
			if (tnodes[par] == NULL) {
				++par;
			}
			else {
				tnodes[par]->left = tnodes[child++];
				tnodes[par++]->right = tnodes[child++];
			}
		}
		return tnodes[0];
	}
};

本代码提交AC,用时72MS。