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 search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just 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.

subject

Serialize deserialize binary search tree ( Try to be as compact as possible )

Ideas

The biggest difference is  “encoded string needs to be as compact as possible”. namely encode Try to be as compact as possible

To makes it the most compact possible,  since we just need the order the values were inserted, we do not need to account for null nodes in the string with "#" or "null".

Hence, the final string contains only the values and separators, which makes it the most compact possible.

1. stay encode When ,don't account for null nodes

2. stay decode When , No more queue To save the whole treenode Information about , It's the size 1 Array of idx Come on track Which one to scan at present node 了 , use idx To get the node value value ( namely mock up a pass-by-address process). adopt BST Of attribute (left < root < right) Come on build tree.

So one of the optimizations we did was ,

stay encode When , No longer root == null Information about encode To string in

The problem is coming. , stay decode When , How to read root == null The node information of ?

use int[] idx = new int[]{0} Go to track The current processing is String[] nodes Number one of them node

utilize BST Of attribute

if such node value < min || > max, It must have crossed the line , return null

Code

 public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
buildString(root, sb);
return sb.toString();
} private void buildString(TreeNode root, StringBuilder sb) {
if (root == null) return;
/*Q: Why not root == null Add to stringbuilder in ?
Since we just need the order the values were inserted, you do not need to account for null nodes in the string with "#" or "null". Hence, the final string contains only the values and
separators, which makes it the most compact possible.
Q: Why do you choose pre-order
preorder traversal When , For the current node , All the left nodes are smaller than him , The right node is bigger than him
*/
sb.append(root.val).append(",");
buildString(root.left, sb);
buildString(root.right, sb);
} // Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.length() == 0) return null;
//
int[] idx = new int[]{0};
idx[0] = 0;
return buildTree(data.split(","), idx, Integer.MIN_VALUE, Integer.MAX_VALUE);
} private TreeNode buildTree(String[] nodes, int[] idx, int min, int max) {
if (idx[0] == nodes.length) return null;
int val = Integer.parseInt(nodes[idx[0]]);
if (val < min || val > max) return null; // Go back if we are over the boundary
TreeNode cur = new TreeNode(val);
idx[0]++; // update current position
/*keep with encode pre-order*/
cur.left = buildTree(nodes, idx, min, val);
cur.right = buildTree(nodes, idx, val, max);
return cur;
}
}

[leetcode]449. Serialize and Deserialize BST Serialize deserialize binary search tree ( Try to be as compact as possible ) More articles about

  1. [leetcode]449. Serialize and Deserialize BST Serialization and deserialization BST

    Serialization is the process of converting a data structure or object into a sequence of bits so tha ...

  2. LeetCode 449. Serialize and Deserialize BST

    The link to the original question is here :https://leetcode.com/problems/serialize-and-deserialize-bst/description/ subject : Serialization i ...

  3. 449 Serialize and Deserialize BST Serialize and deserialize binary search trees

    See :https://leetcode.com/problems/serialize-and-deserialize-bst/description/ C++: /** * Definition fo ...

  4. [leetcode]449. Serialize and Deserialize BST Design BST The codec

    I learned something from this problem . /* I started thinking about middle order traversal , But when I decoded it, I found that , Middle order traversal does not uniquely determine the binary tree . Later I read the answers on the Internet , It is found that preorder traversal is possible , Have a look at , about BST, Preorder traversal is really possible The only way to be sure . ...

  5. Java Realization LeetCode 449 Serialize and deserialize binary search trees

    449. Serialize and deserialize binary search trees Serialization is the process of converting a data structure or object into a series of bits , So that it can be stored in a file or memory buffer , Or through a network link , To rebuild later in the same or another computer environment . Design an algorithm ...

  6. 【leetcode-449】 Serialize and deserialize binary search trees

    Serialization is the process of converting a data structure or object into a series of bits , So that it can be stored in a file or memory buffer , Or through a network link , To rebuild later in the same or another computer environment . Design an algorithm to serialize and deserialize the binary search tree . On the sequence ...

  7. 【leetcode】449. Serialize and Deserialize BST

    The title is as follows : Serialization is the process of converting a data structure or object into a sequence of bits ...

  8. 449. Serialize and Deserialize BST

    https://leetcode.com/problems/serialize-and-deserialize-bst/#/description Serialization is the proce ...

  9. 449. Serialize and Deserialize BST—— Almost all tree interview questions will come back to BFS perhaps DFS, Use BFS,None Node storage #

    Serialization is the process of converting a data structure or object into a sequence of bits so tha ...

Random recommendation

  1. GitHub English used

    1.Github home page Pull requests   Issues Gist request problem The main points of Learn Git and GitHub without any code! No code learning Git and GitHu ...

  2. ios--uitextfield Dynamically limit the number of words entered ( Solution )

    1. Define an event : -(IBAction)limitLength:(UITextField *)sender { bool isChinese;// Infer whether the current input method is Chinese if ([[[UIText ...

  3. DELPHI Take the file name and extension

    x:=ExtractFileName(str);  // Take file name + Extension , Does not contain file path  y:=ExtractFileExt(str);   // Take the file extension

  4. Mathematical concepts ——J - number theory , Prime factor decomposition

    J -  number theory , Prime factor decomposition Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit ...

  5. iOS Push Certificate p12 Turn into pem

    First you need to export p12 Certificate in format , Please refer to the following for specific operation : Secondly, you can convert it by inputting the following command in the console : openssl pkcs12 -in You exported p12 certificate -out What you want to convert pem certificate -nod ...

  6. three.js Source code ( sixteen )Math/Frustum.js

    The business world is boundless (http://blog.csdn.net/omni360/) This article follows " A signature - Non commercial use - bring into correspondence with " Create a common agreement Please keep this sentence : The business world is boundless -   This blog focuses on   agile development ...

  7. [Python]Codecombat Dungeon of strategy Kithgard(1-22 Turn off )

    home page :https://cn.codecombat.com/play Language :Python The first interface : Dungeon Kithgard(22 Turn off ) Time :1-3 Hours Content : grammar . Method . Parameters . character string . loop . Variable etc. Webpage : ...

  8. How do I confirm online CLOSE_WAIT The reason and how to solve it .

    1. This paper Internal architecture :Tomcat Applications ---> nginx ---> other Tomcat Applications , Inside Tomcat Application passed nginx Call other applications . HTTP plug-in unit :HttpClient 4. ...

  9. [Codeforces 864C]Bus

    Description A bus moves along the coordinate line Ox from the point x = 0 to the point x = a. After ...

  10. MyEclipse Report errors :Errors running builder &#39;DeploymentBuilder&#39; on project &#39; project name &#39;

    No replacement MyEclipse edition , It's just that I unloaded it again , And then they report errors , Refer to the articles on the Internet Solve the version  . Delete the deployment file under the project