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 5as “[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.
Binary Tree Serialization Algorithm using Depth First Search (Inorder Traversal)
The easiest way to serialize a binary tree is to use the depth first search (which is usually implemented using Recursion) to perform a in-order traversal. For example the following binary tree will be serialized into “1(2)(3)”
1 / \ 2 3
In the form of “ROOT(LEFT)(RIGHT)” or “ROOT(LEFT)” where the right definition can be omitted if it is null. The LEFT and RIGHT tree definitions are recursive as well.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | /** * 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: // Encodes a tree to a single string. string serialize(TreeNode* root) { if (root == nullptr) { return ""; } string s = std::to_string(root->val) + "(" + serialize(root->left) + ")"; if (root->right != nullptr) { s += "(" + serialize(root->right) + ")"; } return s; } } |
/**
* 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:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == nullptr) {
return "";
}
string s = std::to_string(root->val) +
"(" + serialize(root->left) + ")";
if (root->right != nullptr) {
s += "(" + serialize(root->right) + ")";
}
return s;
}
}The recursive binary tree seralization algorithm is much straightforward.
Binary Tree DeSerialization Algorithm
The de-serialization process is a bit tricky, which we already discussed in this post: How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)
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 | /** * 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: // Decodes your encoded data to tree. TreeNode* deserialize(string data) { string s = data; if (s.size() == 0) { return nullptr; } if (s[0] == ')') return nullptr; int j = 0; while (j < s.size() && s[j] != '(') j ++; TreeNode* root = new TreeNode(std::stoi(s.substr(0, j))); int left = 0, i = j; // find separation between left and right definition while (i < s.size()) { if (s[i] == '(') { left ++; } else if (s[i] == ')') { left --; } if (left == 0) { break; } i ++; } if (j < s.size() - 1) { root->left = deserialize(s.substr(j + 1, i - 1 - j)); } if (i + 1 < s.size() - 1) { root->right = deserialize(s.substr(i + 2, s.size() - i - 2)); } return root; } }; |
/**
* 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:
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
string s = data;
if (s.size() == 0) {
return nullptr;
}
if (s[0] == ')') return nullptr;
int j = 0;
while (j < s.size() && s[j] != '(') j ++;
TreeNode* root = new TreeNode(std::stoi(s.substr(0, j)));
int left = 0, i = j;
// find separation between left and right definition
while (i < s.size()) {
if (s[i] == '(') {
left ++;
} else if (s[i] == ')') {
left --;
}
if (left == 0) {
break;
}
i ++;
}
if (j < s.size() - 1) {
root->left = deserialize(s.substr(j + 1, i - 1 - j));
}
if (i + 1 < s.size() - 1) {
root->right = deserialize(s.substr(i + 2, s.size() - i - 2));
}
return root;
}
};–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)
Next Post: WXT pre-sale is now live - is it worth it?
