Binarytree practice binary tree serialization and deserialization 606, 331, 652, 297

297. Serialization and deserialization of binary trees

Serialization is the operation of converting a data structure or object into consecutive bits , Then the transformed data can be stored in a file or memory , It can also be transmitted to another computer environment through the network , Reconstruct the original data in the opposite way .

Please design an algorithm to realize the serialization and deserialization of binary tree . There's no limit to your sequence / Deserialization algorithm execution logic , You just need to make sure that a binary tree can be serialized into a string and that the string can be deserialized into the original tree structure .
Answer key ：
1）BFS
serialize ： Universal BFS
Deserialization ： Every time I traverse 2 Nodes this 2 The first node is the left and right children of the out of line node

2）DFS recursive （ Draw and write
serialize ： Find the preorder traversal sequence of binary tree
Deserialization ： The sequenced traversal sequence obtained by serialization Build the original binary tree

sloution：
1）BFS serialize ： queue

 public String serialize(TreeNode root) {
    
        if(root==null){
    
            return "";
        }
        StringBuilder res=new StringBuilder();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
    
            TreeNode cur=queue.poll();
            if(cur==null){
    
                res.append("null,");
            }
            else{
    
               res.append(String.valueOf(cur.val));
               res.append(",");
               queue.offer(cur.left);
               queue.offer(cur.right);
            }
        }  
        return res.toString();
    }
 author ：carryzz

BFS Deserialization ：

    public TreeNode deserialize(String data) {
    
        if(data.equals("")){
    
            return null;
        }
        String []temp=data.split(",");
        TreeNode root=new TreeNode(Integer.valueOf(temp[0]));
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);// First queue node 
        TreeNode cur=root;
        
        for(int i=1;i<temp.length;){
    
            cur=queue.poll();// Exit node   Traverse its left and right children 
            if(!temp[i].equals("null")){
    
                cur.left=new TreeNode(Integer.valueOf(temp[i]));
                queue.offer(cur.left);

            }
            i+=1;
            if(!temp[i].equals("null")){
    
                cur.right=new TreeNode(Integer.valueOf(temp[i]));
                queue.offer(cur.right);
            }
            i+=1;
        }
        return root;
    }
}

 author ：carryzz

2）DFS serialize ： Search for the first order traversal

public class Codec {
    
    public String serialize(TreeNode root) {
    
        StringBuilder res=mySeri(root,new StringBuilder());
        return res.toString();
    }

    StringBuilder mySeri(TreeNode root,StringBuilder sb){
    
        if(root==null){
    
            sb.append("null,");
            return sb;
        }
        else if(root!=null){
    
            sb.append(root.val);
            sb.append(",");
            
            mySeri(root.left,sb);
            mySeri(root.right,sb);
        }
        return sb;
    }

 author ：carryzz

DFS Deserialization ：

 public TreeNode deserialize(String data) {
    
        String []temp=data.split(","); //  Convert the serialized result into a string array 
        List<String> list=new LinkedList<>(Arrays.asList(temp)); //  Convert string array to collection class   Easy to operate 
        return myDeSeri(list);
    }
    public TreeNode myDeSeri(List<String> list){
    
        TreeNode root;
        if(list.get(0).equals("null")){
    
            list.remove(0); //  Delete first element   Then the second element becomes the new header   Easy recursion  
            return null;
        }
        else{
    
            root=new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            root.left=myDeSeri(list);
            root.right=myDeSeri(list);
        }
        return root;
    }
}

 author ：carryzz

/**
* Functions for building trees buildTree Received “ state ” yes list Array , From serialized string to
* In the order of previous traversal ： First build the root node , Then build the left subtree 、 Right subtree
* take list The first item of the array pops up , It is the of the current subtree root node
* If it is ‘X’ , return null
* If it's not for ‘X’, Then create a node for it , And recursively call buildTree Construct left and right subtrees , The current subtree has been built , Back up
*/

        public TreeNode deserialize(String data) {
    
            String[] temp = data.split(",");
            Deque<String> dp = new LinkedList<>(Arrays.asList(temp));
            return buildTree(dp);
        }
        private TreeNode buildTree(Deque<String> dq){
    
            String s = dq.poll(); // Returns the current node 
            if (s.equals("X")) return null;
            TreeNode node = new TreeNode(Integer.parseInt(s));
            node.left = buildTree(dq); // Build the left subtree 
            node.right = buildTree(dq); // Build the right subtree 
            return node;
        }
    }

notes ：

1）Queue in remove() and poll() Are used to remove an element from the queue header . When the queue element is empty ,remove() The method will throw away NoSuchElementException abnormal ,poll() Method only returns null .

2）Queue in add() and offer() Are used to add an element to the queue . When the capacity is full ,add() Method will throw IllegalStateException abnormal ,offer() Method only returns false .

3）String.valueOf(int i) : take int Variable i Convert to string

4）toString(): Return to indicate Integer It's worth it String object .

5)Integer. valueOf() The role of methods
Integer. valueOf() The basic types can be int Convert to package type Integer
Or will String convert to Integer,String If Null or “” All will report wrong.

6）split Split string
1、 If you use “.” As a word of separation , It must be written as follows ：String.split("\."), In order to separate them correctly , Out-of-service String.split(".");
2、 If you use “|” As a word of separation , It must be written as follows ：String.split("\|"), In order to separate them correctly , Out-of-service String.split("|");
“.” and “|” All escape characters , Must add "\";

7）Arrays.asList() Convert an array to a List object , This method will return a ArrayList Object of type .

331. Verify the preorder serialization of a binary tree

One way to serialize a binary tree is to use preorder traversal . When we come across a non empty node , We can record the value of this node . If it's an empty node , We can use a tag value record , for example #.

for example , The above binary tree can be serialized as a string “9,3,4,#,#,1,#,#,2,#,6,#,#”, among # Represents an empty node .

Given a comma separated sequence , Verify that it is the correct preorder serialization of the binary tree . Write a feasible algorithm without reconstructing the tree .

Each character separated by a comma is either an integer or a representation null Pointer ‘#’ .

You can think that the input format is always valid , For example, it will never contain two consecutive commas , such as “1,3” .

Example 1:

Input : “9,3,4,#,#,1,#,#,2,#,6,#,#”
Output : true
Example 2:

Input : “1,#”
Output : false
Example 3:

Input : “9,#,#,1”
Output : false

Answer key ：
1） Convert string to character array for easy operation
2） The number of leaf nodes is different from that of non leaf nodes 1
sloution：

class Solution {
    
    public boolean isValidSerialization(String preorder) {
    
    String[] str = preorder.split(",");
    int nnum=0;
    int inum=0;

    for(int i=0;i<str.length;i++){
    
    if(nnum> inum) return false;
    if(str[i].equals("#")) nnum++;
    else inum++;
    }
    return (nnum - inum) == 1;
    }
}

606. Create a string from a binary tree

You need to do a pre traversal , Convert a binary tree to a string of parentheses and integers .
Empty nodes use a pair of empty brackets “()” Express . And you need to omit all empty bracket pairs that do not affect the one-to-one mapping between the string and the original binary tree .
Answer key ： Use when the left subtree is empty () Replace node , If the right subtree is empty or both the left and right subtrees are empty, do not .

Reference resources sloution：

class Solution {
    
    // The former sequence traversal 
    TreeNode pre = null;

    public String tree2str(TreeNode t) {
    
        if (t == null) return "";
        StringBuilder sb = new StringBuilder();
        helper(t, pre, sb);
        return sb.substring(1, sb.length() - 1);
    }

    private void helper(TreeNode root, TreeNode pre, StringBuilder sb) {
    
        if (root == null) return;
        // The former sequence traversal 
        //1. If the current node is the right subtree of the parent node and the left subtree is empty , Brackets cannot be omitted 
        if (pre != null && pre.left == null && pre.right == root) {
    
            sb.append("()");
        }
        sb.append("(").append(root.val);
        pre = root;
        helper(root.left, pre, sb);
        helper(root.right, pre, sb);
        // Close parentheses after traversing the current node 
        sb.append(")");
    }
}

The operation speed is relatively high （ Usually ）：
StringBuilder > StringBuffer > String

String yes final Class cannot be inherited and is a string constant , and StringBuilder and StringBuffer Are string variables .String Once an object is created, it cannot be changed , The latter two are modifiable , They can only build objects through constructors , And after the object is created, memory space will be allocated in memory , And initially save one null, adopt append Method direction StringBuffer and StringBuilder Assignment in .

Quote from ：String,StringBuilder and StringBuffer
652【hashmap】