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。