Problem:
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.
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
Idea:
Recursion
Time Complexity O(n)
Solution 1: ASCII
C++
|
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 |
// Author: Huahua // Running time: 39 ms class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { ostringstream out; serialize(root, out); return out.str(); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { istringstream in(data); return deserialize(in); } private: void serialize(TreeNode* root, ostringstream& out) { if (!root) { out << "# "; return; } out << root->val << " "; serialize(root->left, out); serialize(root->right, out); } TreeNode* deserialize(istringstream& in) { string val; in >> val; if (val == "#") return nullptr; TreeNode* root = new TreeNode(stoi(val)); root->left = deserialize(in); root->right = deserialize(in); return root; } }; |
Solution 2: Binary
C++
|
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 |
// Author: Huahua // Running time: 23 ms (beat 98.07%) class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { ostringstream out; serialize(root, out); return out.str(); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { istringstream in(data); return deserialize(in); } private: enum STATUS { ROOT_NULL = 0x0, ROOT = 0x1, LEFT = 0x2, RIGHT = 0x4 }; void serialize(TreeNode* root, ostringstream& out) { char status = 0; if (root) status |= ROOT; if (root && root->left) status |= LEFT; if (root && root->right) status |= RIGHT; out.write(&status, sizeof(char)); if (!root) return; out.write(reinterpret_cast<char*>(&(root->val)), sizeof(root->val)); if (root->left) serialize(root->left, out); if (root->right) serialize(root->right, out); } TreeNode* deserialize(istringstream& in) { char status; in.read(&status, sizeof(char)); if (!status & ROOT) return nullptr; auto root = new TreeNode(0); in.read(reinterpret_cast<char*>(&root->val), sizeof(root->val)); root->left = (status & LEFT) ? deserialize(in) : nullptr; root->right = (status & RIGHT) ? deserialize(in) : nullptr; return root; } }; // Your Codec object will be instantiated and called as such: // Codec codec; // codec.deserialize(codec.serialize(root)); |
C++ (string)
|
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 |
// Author: Huahua // Running time: 23 ms (<98.13%) class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { string s; serialize(root, s); return s; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { int pos = 0; return deserialize(data, pos); } private: enum STATUS { ROOT_NULL = 0x0, ROOT = 0x1, LEFT = 0x2, RIGHT = 0x4 }; void serialize(TreeNode* root, string& s) { char status = ROOT_NULL; if (root) status |= ROOT; if (root && root->left) status |= LEFT; if (root && root->right) status |= RIGHT; s.push_back(status); if (!root) return; s.append(reinterpret_cast<char*>(&root->val), sizeof(root->val)); if (root->left) serialize(root->left, s); if (root->right) serialize(root->right, s); } TreeNode* deserialize(const string& s, int& pos) { char status = s[pos++]; if (!status) return nullptr; TreeNode* root = new TreeNode(0); memcpy(&root->val, s.data() + pos, sizeof(root->val)); pos += sizeof(root->val); root->left = (status & LEFT) ? deserialize(s, pos) : nullptr; root->right = (status & RIGHT) ? deserialize(s, pos) : nullptr; return root; } }; |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment