Serialization is 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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Example 1:
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The input tree is guaranteed to be a binary search tree.
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassCodec:defserialize(self,root:Optional[TreeNode])->str:"""Encodes a tree to a single string."""defdfs(root:Optional[TreeNode]):ifrootisNone:returnnums.append(root.val)dfs(root.left)dfs(root.right)nums=[]dfs(root)return" ".join(map(str,nums))defdeserialize(self,data:str)->Optional[TreeNode]:"""Decodes your encoded data to tree."""defdfs(mi:int,mx:int)->Optional[TreeNode]:nonlocaliifi==len(nums)ornotmi<=nums[i]<=mx:returnNonex=nums[i]root=TreeNode(x)i+=1root.left=dfs(mi,x)root.right=dfs(x,mx)returnrootnums=list(map(int,data.split()))i=0returndfs(-inf,inf)# Your Codec object will be instantiated and called as such:# Your Codec object will be instantiated and called as such:# ser = Codec()# deser = Codec()# tree = ser.serialize(root)# ans = deser.deserialize(tree)# return ans
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */publicclassCodec{privateinti;privateList<String>nums;privatefinalintinf=1<<30;// Encodes a tree to a single string.publicStringserialize(TreeNoderoot){nums=newArrayList<>();dfs(root);returnString.join(" ",nums);}// Decodes your encoded data to tree.publicTreeNodedeserialize(Stringdata){if(data==null||"".equals(data)){returnnull;}i=0;nums=Arrays.asList(data.split(" "));returndfs(-inf,inf);}privatevoiddfs(TreeNoderoot){if(root==null){return;}nums.add(String.valueOf(root.val));dfs(root.left);dfs(root.right);}privateTreeNodedfs(intmi,intmx){if(i==nums.size()){returnnull;}intx=Integer.parseInt(nums.get(i));if(x<mi||x>mx){returnnull;}TreeNoderoot=newTreeNode(x);++i;root.left=dfs(mi,x);root.right=dfs(x,mx);returnroot;}}// Your Codec object will be instantiated and called as such:// Codec ser = new Codec();// Codec deser = new Codec();// String tree = ser.serialize(root);// TreeNode ans = deser.deserialize(tree);// return ans;
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classCodec{public:// Encodes a tree to a single string.stringserialize(TreeNode*root){if(!root){return"";}stringdata="";function<void(TreeNode*)>dfs=[&](TreeNode*root){if(!root){return;}data+=to_string(root->val)+" ";dfs(root->left);dfs(root->right);};dfs(root);data.pop_back();returndata;}// Decodes your encoded data to tree.TreeNode*deserialize(stringdata){if(data.empty()){returnnullptr;}vector<int>nums=split(data,' ');inti=0;function<TreeNode*(int,int)>dfs=[&](intmi,intmx)->TreeNode*{if(i==nums.size()||nums[i]<mi||nums[i]>mx){returnnullptr;}intx=nums[i++];TreeNode*root=newTreeNode(x);root->left=dfs(mi,x);root->right=dfs(x,mx);returnroot;};returndfs(INT_MIN,INT_MAX);}vector<int>split(conststring&s,chardelim){vector<int>tokens;stringstreamss(s);stringtoken;while(getline(ss,token,delim)){tokens.push_back(stoi(token));}returntokens;}};// Your Codec object will be instantiated and called as such:// Codec* ser = new Codec();// Codec* deser = new Codec();// string tree = ser->serialize(root);// TreeNode* ans = deser->deserialize(tree);// return ans;
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */typeCodecstruct{}funcConstructor()Codec{returnCodec{}}// Serializes a tree to a single string.func(this*Codec)serialize(root*TreeNode)string{ifroot==nil{return""}data:=&strings.Builder{}vardfsfunc(*TreeNode)dfs=func(root*TreeNode){ifroot==nil{return}data.WriteString(strconv.Itoa(root.Val))data.WriteByte(' ')dfs(root.Left)dfs(root.Right)}dfs(root)returndata.String()[0:data.Len()-1]}// Deserializes your encoded data to tree.func(this*Codec)deserialize(datastring)*TreeNode{ifdata==""{returnnil}vals:=strings.Split(data," ")i:=0vardfsfunc(int,int)*TreeNodedfs=func(mi,mxint)*TreeNode{ifi==len(vals){returnnil}x,_:=strconv.Atoi(vals[i])ifx<mi||x>mx{returnnil}i++root:=&TreeNode{Val:x}root.Left=dfs(mi,x)root.Right=dfs(x,mx)returnroot}returndfs(math.MinInt64,math.MaxInt64)}/** * Your Codec object will be instantiated and called as such: * ser := Constructor() * deser := Constructor() * tree := ser.serialize(root) * ans := deser.deserialize(tree) * return ans */