Please implement two functions to serialize and deserialize the binary tree respectively.

You need to design an algorithm to realize the serialization and deserialization of binary tree. There is no restriction on the execution logic of your sequence / deserialization algorithm. You only need to ensure that a binary tree can be serialized into a string and deserialize the string into the original tree structure.

Note: the input / output format is the same as that currently used by LeetCode. For details, please refer to the format of LeetCode serialized binary tree. You don't have to take this approach, you can also take other methods to solve the problem.

Example:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

analysis:

Because this problem does not limit the execution logic, it can cheat. Directly store the binary tree during serialization and output it during deserialization. But after all, it is a speculative method, which is not recommended. Since it is an algorithm problem, it must be solved by algorithm.

Method: BFS

It does not limit the execution logic, which means that whether we are depth first (DFS) or breadth first (BFS), but to return the string type, it must involve the use of StringBuilder, and DFS involves recursion, which is inconvenient to use, so I use BFS here.

Serialization method: define "queue" and "StringBuilder", and directly store the header node into the queue and StringBuilder. If the left / right node is empty, it will not enter the queue, and StringBuilder will add "null". If it is not empty, it will enter the queue and add the corresponding number in StringBuilder.

Deserialization method: because it is breadth first, the left and right nodes must appear in pairs. Therefore, in addition to the head node, every other two nodes are the left and right nodes of the current node. You only need to judge whether it is empty into the stack.

Time complexity: O(n)
Space complexity: O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    public String serialize(TreeNode root) {
        //Empty tree judgment
        if(root == null){
            return "[]";
        }
        //Create queue
        Deque<TreeNode> queue = new ArrayDeque<>();
        //Define StringBuilder for string operations
        StringBuilder sb = new StringBuilder();
        //Add previous blank number and first value
        sb.append("[");
        sb.append(root.val);
        //Queue stacking
        queue.offerLast(root);
        //Breadth traversal
        while(!queue.isEmpty()){
            //Queue out of stack
            TreeNode node = queue.pollFirst();
            //Add comma
            sb.append(",");
            //Empty: add null to the string, non empty: add the left node value to the stack and the left node value to the string.
            if(node.left != null){
                sb.append(node.left.val);
                queue.offerLast(node.left);
            }else{
                sb.append("null");
            }
            //Add comma
            sb.append(",");
            //Empty: add null to the string, non empty: add the right node value to the stack and the right node value to the string.
            if(node.right != null){
                sb.append(node.right.val);
                queue.offerLast(node.right);
            }else{
                sb.append("null");
            }
        }
        //Add back bracket
        sb.append("]");
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        //If "[]" returns null
        if(data == "[]"){
            return null;
        }
        //String to "[]" and press "," slice
        String[] ss = data.substring(1, data.length()-1).split(",");
        //Define queue
        Deque<TreeNode> queue = new ArrayDeque<>();
        //The first element on the stack
        TreeNode first = new TreeNode(Integer.parseInt(ss[0]));
        queue.offerLast(first);
        //Define index
        int i = 1;
        while(i < ss.length){
            //Out of stack node
            TreeNode node = queue.pollFirst();
            //Judge whether the left node corresponding to the array is empty. If not, add it into the stack
            if(!ss[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(ss[i]));
                queue.offerLast(node.left);
            }
            //Judge whether the right node corresponding to the array is empty. If not, add it into the stack
            if(!ss[i+1].equals("null")){
                node.right = new TreeNode(Integer.parseInt(ss[i+1]));
                queue.offerLast(node.right);
            }
            i+=2;
        }
        return first;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Title Source: LeetCode
Link: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof