leetCode Question: 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
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.

Analysis:

In this problem, I have implemented a differrent way of serialization (in C++ code shown below). If you would like to see the simple version which is the same way of LeetCode OJ, please check out the pyhton code below.

Let's first see the simple way of doing this. We will encode the node value level by level, and only encode the "Null" (or "None" in python) node when it is a leaf node. Since we are "searching" the tree level by level, DFS is usually a good way to do so. Here in my solution, I choose to use two queues, to store nodes in current level, and nodes in next level, respectively. For the deserialization, we could still keep two queues for the BFS, and keep track of the node we are expanding.

Secondly, I'l like to show the implementation using a different way. Although it is not a quite efficient method, it still provides good practice of binary tree and binary tree traversal. Particularly, we have a binary tree, rather than the level by level traversal, we still have three depth-first traversal: preorder, inorder, and postorder. Therefore, we could use preorder and inorder traversal to reconstruct the binary tree. Please take a look at my previous post for details. Note that in this problem, there might be duplicate values in different nodes, we have to use the indices of each node for the traversal. So, our encoding format is: "preorder string;inorder string;value string". The "preorder string" is the indices of each node in preorder order, actually, I have given the sequence from 1 to the number of nodes in this string for simplicity. The "inorder string" is the indices of each node in inorder order. The "vaule string" is the values of each node (using preorder order) in string format. All the elements in three strings are splited using ",".

Code (C++):

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

*/

class Codec {

public:

TreeNode* reconstruct(vector<int>& in, vector<int>& pre, int st, int ed, int& idx, vector<int>& val){

if (idx!=pre.size()){

TreeNode* node = new TreeNode(val[pre[idx]]);

int i=st;

for ( ;i<ed;i++){

if (in[i]==pre[idx]){break;}

}

idx++;

if (i-1 >=st){

node->left = reconstruct(in, pre, st, i-1, idx,val);

}else{

node->left = NULL;

}

if (ed >= i+1){

node->right = reconstruct(in, pre, i+1,ed, idx,val);

}else{

node->right = NULL;

}

return node;

}else{

return NULL;

}

}

void inOrder(TreeNode* root, string& res, string& val, int& i){

if (!root){return;}

inOrder(root->left, res, val, i);

val += to_string(root->val) + ',';

root->val = i;

res += to_string(i) + ',';

i++;

inOrder(root->right,res, val, i);

}

void preOrder(TreeNode* root, string& res){

if (!root){ return; }

res += to_string(root->val) + ',';

preOrder(root->left, res);

preOrder(root->right,res);

}

// Encodes a tree to a single string.

string serialize(TreeNode* root) {

//inorder

string in; //store the inorder tree traversal using index NOT!!! the actural value

string val; //store the actural values of each node according to the "inorder" order

int i=0;

inOrder(root, in, val, i); //inorder traversal

//preorder

string pre; //stroe the preorder tree traversal using index NOT!!! the actural value

preOrder(root, pre); //preorder traversal

//return the encoded string: inorder(index);preorder(index);values

// e.g., Tree [1,2,3,null,null,4,5] returns "0,1,2,3,4,;1,0,3,2,4,;2,1,4,3,5,"

return in + ";" + pre+ ";" + val;

}

// Decodes your encoded data to tree.

TreeNode* deserialize(string data) {

// decode the string

int pos_1 = data.find(';');

string in = data.substr(0,pos_1);

string tmp = data.substr(pos_1+1);

int pos_2 = tmp.find(';');

string pre = tmp.substr(0,pos_2);

string val = tmp.substr(pos_2+1);

vector<int> in_vec; // save the index of inorder traversal

vector<int> pre_vec; // save the index of preorder traversal

vector<int> val_vec; // save the values according to the inorder order

while (val.find(',')!=-1){

val_vec.push_back(stoi(val.substr(0,val.find(','))));

val = val.substr(val.find(',')+1);

}

while (in.find(',')!=-1){

in_vec.push_back(stoi(in.substr(0,in.find(','))));

in = in.substr(in.find(',')+1);

}

while (pre.find(',')!=-1){

pre_vec.push_back(stoi(pre.substr(0,pre.find(','))));

pre = pre.substr(pre.find(',')+1);

}

// reconstruct tree using preorder and inoreder traversal

int idx = 0;

return reconstruct(in_vec, pre_vec, 0, in_vec.size(),idx, val_vec);

}

};

// Your Codec object will be instantiated and called as such:

// Codec codec;

// codec.deserialize(codec.serialize(root));

Code (Python):

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

class Codec:

def serialize(self, root):

"""Encodes a tree to a single string.

:type root: TreeNode

:rtype: str

"""

q1 = []

q2 = []

res = ""

q1.append(root)

while True:

while len(q1) != 0:

tmp = q1.pop(0)

if tmp is None:

res += "null,"

else:

res += str(tmp.val) + ","

q2.append(tmp.left)

q2.append(tmp.right)

if len(q2) == 0:

break

q1 = q2[:]

q2 = []

return res

def deserialize(self, data):

"""Decodes your encoded data to tree.

:type data: str

:rtype: TreeNode

"""

data_list = data[0:-1].split(',') # [0:-1] eliminates the last ','

mp1 = []

mp2 = []

head = None

if data_list[0] != "null":

mp1.append(TreeNode(int(data_list[0])))

head = mp1[0]

i = 1

while i < len(data_list):

for node in mp1:

if node is not None:

if data_list[i] != "null":

node.left = TreeNode(int(data_list[i]))

i+=1

mp2.append(node.left)

if data_list[i] != "null":

node.right = TreeNode(int(data_list[i]))

i+=1

mp2.append(node.right)

mp1 = mp2[:]

mp2 = []

return head

# Your Codec object will be instantiated and called as such:

# codec = Codec()

# codec.deserialize(codec.serialize(root))