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.
Clarification: The input/output 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.
Example 1:
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = [] Output: []
Example 3:
Input: root = [1] Output: [1]
Example 4:
Input: root = [1,2] Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range
[0, 104]
. -1000 <= Node.val <= 1000
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 | /** * 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 { void serialize(TreeNode* node, stringstream &ss){ if(!node) { ss<<"# "; } else { ss<<node->val<<" "; serialize(node->left, ss); serialize(node->right, ss); } } TreeNode* deserialize(stringstream &ss) { string s; ss>>s; if(s=="#"){ return NULL; }else{ TreeNode* node = new TreeNode(stoi(s)); node->left = deserialize(ss); node->right = deserialize(ss); return node; } } public: // Encodes a tree to a single string. string serialize(TreeNode* root) { stringstream ss; serialize(root, ss); return ss.str(); } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { stringstream ss; ss<<data; return deserialize(ss); } }; // Your Codec object will be instantiated and called as such: // Codec codec; // codec.deserialize(codec.serialize(root)); |
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 | /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Codec { String str; String[] strs; int index = 0; // Encodes a tree to a single string. public String serialize(TreeNode root) { str = ""; sh(root); return str; } void sh(TreeNode node){ if(str.length()>0) str += ","; if(node==null){ str += "#"; }else{ str += node.val; sh(node.left); sh(node.right); } } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { strs = data.split(","); index = 0; return dh(); } TreeNode dh(){ TreeNode node; String s = strs[index++]; if(s.equals("#")){ node = null; }else{ node = new TreeNode(Integer.parseInt(s)); node.left = dh(); node.right = dh(); } return node; } } // Your Codec object will be instantiated and called as such: // Codec ser = new Codec(); // Codec deser = new Codec(); // TreeNode ans = deser.deserialize(ser.serialize(root)); |
No comments:
Post a Comment