Serialize and Deserialize Binary Tree

發表於   |   分類於

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.

For example, you may serialize the following tree

1
2
3
4
5
  1
 / \
2   3
   / \
  4   5

as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ 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.

这个题目的设置条件……我个人认为对C++不是很友好就是了，最后用C解决了，用了一个小小的协议，并使用节点的地址作为唯一标识符来使用。

就我个人对网络那点贫瘠的理解来讲，序列化与反序列化其实就是一个“协议”的问题：根据某个协议将数据编码成一个流发出去，然后再根据协议解析接收到的数据流，完成数据的创建。

在碰到这个题目的之前恰好做了HiHoCoder一个类似的题目，就是还原二叉树的，题目在这里。

两题的思路是一样的：从前序遍历和中序遍历还原整个二叉树。当然本题还可以通过层序来恢复就是了。

然而问题出在：HiHo的用例中，所有的二叉树结点的标识都是唯一的，而LeetCode则不唯一，因此在查找中序序列中的节点的过程是很需注意的。

放上AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
typedef struct TreeNode TreeNode;

typedef struct Protocol
{
	TreeNode* addr;
	int val;
}Protocol;

typedef struct DynArray
{
    int size;
    int cap;
    Protocol* array;
}DynArray;

void array_init(DynArray* a)
{
    a->size = 0;
    a->cap = 0;
    a->array = NULL;
}

void array_insert(DynArray* a, Protocol* p)
{
    if (a->array == NULL)
    {
        a->cap = 1;
        a->array = (Protocol*)malloc(sizeof(Protocol));
    }
    else
    {
        if (a->cap == a->size)
        {
            a->cap *= 2;
            Protocol* narray = (Protocol*)malloc(a->cap*sizeof(Protocol));
            for (int i = 0; i < a->size; ++i)
            {
                narray[i].addr = a->array[i].addr;
                narray[i].val = a->array[i].val;
            }
            free(a->array);
            a->array = narray;
        }
    }
    a->array[a->size].addr = p->addr;
    a->array[a->size].val = p->val;
    a->size++;
}

void preOrder(TreeNode* root, DynArray* a)
{
    if (root)
    {
        Protocol p;
        p.addr = root;
        p.val = root->val;
        array_insert(a,&p);

        preOrder(root->left,a);
        preOrder(root->right,a);
    }
}

void inOrder(TreeNode* root, DynArray* a)
{
    if (root)
    {
        inOrder(root->left,a);

        Protocol p;
        p.addr = root;
        p.val = root->val;
        array_insert(a,&p);

        inOrder(root->right,a);
    }
}

int findInOrder(TreeNode* addr, Protocol* address, int len)
{
    for(int i = 0 ; i < len; ++i)
    {
        if (address[i].addr == addr)
        {
            return i;
        }
    }
    return 0;
}

TreeNode* reBuild(Protocol* pre, Protocol* in, int* index, int begin, int end, int len)
{
    if (begin < end)
    {
        * index +=1;
        TreeNode* r = (TreeNode*)malloc(sizeof(TreeNode));
        r->val = pre[* index].val;
        r->left = NULL;
        r->right = NULL;
        int pos = findInOrder(pre[* index].addr,in,len);
        r->left = reBuild(pre,in,index,begin,pos-1,len);
        r->right = reBuild(pre,in,index,pos+1,end,len);
        return r;
    }
    else if (begin == end)
    {
        * index += 1;
        TreeNode* r = (TreeNode*)malloc(sizeof(TreeNode));
        r->left = NULL;
        r->right = NULL;
        r->val = pre[* index].val;
        return r;
    }
    else
    {
        return NULL;
    }
}

char* serialize(struct TreeNode* root) {
    DynArray* result = (DynArray*)malloc(sizeof(DynArray));
    array_init(result);
    preOrder(root,result);
    inOrder(root,result);
    return (char*)result;
}

struct TreeNode* deserialize(char* data) {
    DynArray* darray = (DynArray*)(data);
    int len = darray->size / 2;
    Protocol* pre = darray->array;
    Protocol* in = darray->array + len;
    int index = -1;
    return reBuild(pre,in,&index,0,len-1,len);
}

再放上HiHo那个题目的AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <string>
using namespace std;

string preOrder;
string inOrder;
string postOrder;

struct BTNode
{
	BTNode* left;
	BTNode* right;
	char data;
	BTNode()
	{
		left = NULL;
		right = NULL;
	}
};

int findRootInMidSeq(char c)
{
	int pos = 0;
	while (true)
	{
		if (inOrder[pos] == c)
		{
			return pos;
		}
		++pos;
	}
	return pos;
}

BTNode* buildTree(int start, int end, int& root)
{
	if (start > end)
	{
		return NULL;
	}
	root += 1;
	if (start == end)
	{
		BTNode* r = new BTNode;
		r->data = preOrder[root];
		return r;
	}
	BTNode* r = new BTNode;
	r->data = preOrder[root];
	int pos = findRootInMidSeq(preOrder[root]);
	r->left = buildTree(start, pos - 1, root );
	r->right = buildTree(pos + 1, end, root );
	return r;
}

void post(BTNode* root)
{
	if (root)
	{
		post(root->left);
		post(root->right);
		postOrder.push_back(root->data);
	}
}

int main(int argc, char** argv)
{
	cin >> preOrder;
	cin >> inOrder;
	int index = -1;
	BTNode* root = buildTree(0, inOrder.length() - 1, index);
	post(root);
	cout << postOrder << endl;
	return 0;
}

以及，类似，然而却RE了的LeetCode代码，其中的findRootIninOrder()函数是不能用在这里的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

class Codec {
public:
	// 序列化为串
	void preOrder(TreeNode* root, string& btree)
	{
		if (root)
		{
			btree.push_back((char)(root->val));
			preOrder(root->left, btree);
			preOrder(root->right, btree);
		}
	}

	void inOrder(TreeNode* root, string& btree)
	{
		if (root)
		{
			inOrder(root->left, btree);
			btree.push_back((char)(root->val));
			inOrder(root->right, btree);
		}
	}

	// 反序列化，实际上就是从前序遍历和后序遍历的结果上把二叉树还原出来
	// 这是一个分治法的应用。

	int findRootIninOrder(char c, string& midStr)
	{
		for (int i = 0; i < midStr.length(); ++i)
		{
			if (midStr[i] == c)
			{
				return i;
			}
		}
	}

	TreeNode* rebuild(int begin, int end, int& index, string& midStr, string& preStr)
	{
		TreeNode* root = NULL;

		if (begin < end)
		{
			++index;
			root = new TreeNode((int)(preStr[index]));
			int pos = findRootIninOrder(preStr[index], midStr);
			root->left = rebuild(begin, pos - 1, index, midStr, preStr);
			root->right = rebuild(pos + 1, end, index, midStr, preStr);

		}
		else if (begin == end)
		{
			++index;
			root = new TreeNode((int)(preStr[index]));
		}
		else
		{
			return NULL;
		}
		return root;
	}


	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		string btree;
		preOrder(root, btree);
		inOrder(root, btree);
		return btree;
	}

	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		string preStr;
		string midStr;
		int btreeSize = data.length() / 2;
		preStr = data.substr(0, btreeSize);
		midStr = data.substr(btreeSize, btreeSize);
		if (preStr.length() == 0)
		{
			return NULL;
		}
		int index = -1;
		return rebuild(0, btreeSize - 1, index, midStr, preStr);
	}
};