[sword finger offer] serialized binary tree

Their thinking

Serialization , You can use various traversal methods , For example, sequence traversal 、 Recursive traversal traverses the binary tree , The value of each node is spliced into a string during traversal , Note that each node is separated by an identifier , for example ,, This is to prevent the value of the node from exceeding single digits .

Deserialization is decoded according to the serialization process , Different ways of deserialization have different skills , Next, sequence traversal and preorder traversal are used to solve .

Solution 1 ： Sequence traversal

• serialize ： Traverse through the queue , Then generate a serialized string , Comparing to conventional .
• Deserialization ： It's a little bit difficult . First of all, res according to , Get by segmentation String Array strs, Each position represents the value of a node . Like serialization , You also need to use a queue to operate , Note that you need to get the array every time strs Two elements in , That is to build the left and right subtrees of the current node , Then add the left and right subtrees to the queue respectively .

import java.util.*;

public class Solution {
    
    String Serialize(TreeNode root) {
    
        String str = "";
        if (root == null)
            return str;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        str += root.val + ",";
        while (!queue.isEmpty()) {
    
            TreeNode top = queue.poll();
            if (top.left == null)
                str += "#";
            else {
    
                queue.add(top.left);
                str += top.left.val;
            }
            str += ',';
            if (top.right == null)
                str += "#";
            else {
    
                queue.add(top.right);
                str += top.right.val;
            }
            str += ',';
        }
        return str;
    }

    TreeNode Deserialize(String str) {
    
        if (str.length() == 0)
            return null;
        int i = 1;
        String strList[] = str.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(strList[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
    
            TreeNode top = queue.poll();
            //  The left subtree 
            if (strList[i].equals("#"))
                top.left = null;
            else {
    
                top.left = new TreeNode(Integer.parseInt(strList[i]));
                queue.add(top.left);
            }
            i++;
            //  Right subtree 
            if (strList[i].equals("#"))
                top.right = null;
            else {
    
                top.right = new TreeNode(Integer.parseInt(strList[i]));
                queue.add(top.right);
            }
            i++;
        }
        return root;
    }
}

Solution 2 ： The first sequence traversal

• serialize ： Define global string res, Record the node value traversed during recursion , After traversing a node , Add... After it , identifier .
• Deserialization ： It's a little bit difficult . First of all, res according to , Get by segmentation String Array strs, Each position represents the value of a node . Define global variables ind, Used to record the current traversal to strs The location of , If the current location is #, Said is empty , Go straight back to null; Otherwise, create a new node node, And recursively construct its left and right subtrees , Be careful , Determine whether the array is out of bounds before recursion , If inds++ After equal to strs The length of , It indicates that the array has been traversed , Return at this time node（ Note that the judgment of array out of bounds cannot be placed at the beginning , Otherwise, I can't write it down , Because I don't know what to return ）

import java.util.*;

public class Solution {
    
    public String res = "";
    public int ind = 0;

    String Serialize(TreeNode root) {
    
        if (root == null) {
    
            res += "#,";
            return res;
        }
        res += root.val + ",";
        Serialize(root.left);
        Serialize(root.right);
        return res;
    }

    TreeNode deserialize(String[] strs) {
    
        if (strs[ind].equals("#")) {
    
            ind++;
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(strs[ind]));
        ind++;
        if (ind >= strs.length)
            return node;
        node.left = deserialize(strs);
        node.right = deserialize(strs);
        return node;
    }

    TreeNode Deserialize(String str) {
    
        String[] strs = str.split(",");
        return deserialize(strs);
    }
}