Serialization and deserialization of binary trees

Reference article: 297. Java BFS sequence traversal

Reference: Alex

The title

Thought analysis

In view of the code in the reference article for thinking analysis, method summary.

Serialize () serialization

Analysis of the

1. Each node is traversed in the preceding order, putting the value into a string if not null, or “null” if null
2. Class members and variables are not allowed, so you can’t iterate recursively
3. Since front-order traversal fits the first-in, first-out principle, we consider using queues to implement front-order traversal
4. The current node is added to the queue to determine whether the node is empty. If not, the current node is dequeued and the value is concatenated to a string. Then the left and right children of the current node are queued
5. If the current node is empty, there is no child node and the “NULL” string is concatenated
6. Repeat steps 4 and 5 until the queue is empty
7. The string is processed and returned

code

public String serialize(TreeNode root) {
        StringBuilder res = new StringBuilder("["); // Concatenated string

        Queue<TreeNode> queue = new LinkedList(); // Save the node queue
        queue.add(root); // Start with the root node

        while(! queue.isEmpty()) { TreeNode cur = queue.remove();// queue first node
            if (cur == null) {
                /* If the node is empty, there is no child node, and null is concatenated into the string */
                res.append("null,");
            } else {
                /* If the node is not empty, the value is added to the string and its left and right nodes are queued */
                res.append(cur.val + ",");
                queue.add(cur.left);
                queue.add(cur.right);
            }
        }

        res.setLength(res.length() - 1); // The value in res will end with an extra comma, so we need to remove the last character
        res.append("]");
        return res.toString();
    }
Copy the code

Deserialize () deserialize

Analysis of the

1. Intercepts and splits a string, returning an array of strings, each of which is a node value
2. Write a method that passes the value of the node and returns the value of the node, or null if the value is “null”
3. At this point we can treat each item in the array as a node
4. The question becomes how do you concatenate each node in the array in the original order
5. Again, the idea is to use queue storage nodes
6. If the left and right children of a parent node are found, we look for the next parent node
7. So our queue should store the parent node that has not yet found the child node
8. So how do you know?Left and right child nodes have been found?
   1. We can use a variableisLeftTo store whether it is the left node
   2. isLeftThe default istrue
   3. Have the parent node connect to the left node, and then pairisLeftIf I take the inverse, thenisLeftforfalse
   4. Then connect the right node to theisLeftIf I take the inverse, thenisLeftfortrue
   5. ifisLeftChange back againtrue, indicating that the left and right child nodes are found
   6. The parent node should then become the head of the queue
9. When the array traversal is complete, the first node of the array is returned

code

public TreeNode deserialize(String data) {
        // Cut and split the string, return an array of strings, each item in the array is a node value
        String[] arr = data.substring(1, data.length() - 1).split(",");

        Queue<TreeNode> queue = new LinkedList<>(); // The store has not found the child's parent
        TreeNode root = getNode(arr[0]); // Save the first node of the array, and finally return it
        TreeNode parent = root; // Temporary parent variable
        boolean isLeft = true; // Determine whether the left and right child nodes have been found

        for (int i = 1; i < arr.length; i++) {
            TreeNode cur = getNode(arr[i]); // go through the number group

            if (isLeft) {
                // cur is the left node of parent
                parent.left = cur;
            } else {
                // cur is the right node of parent
                parent.right = cur;
            }

            if(cur ! =null) {
                Cur is a parent node, but its left and right children may be emptyqueue.add(cur); } isLeft = ! isLeft;/ / the not

            if (isLeft) {
                /* If true, the cur node is the right node, and the left and right nodes have found the first queue, save as the new parent node */parent = queue.poll(); }}return root;
    }

    /** * returns the node * with the value val@paramVal If val is "null", null * is returned@returnReturns the node */ with the value val
    private TreeNode getNode(String val) {
        if (val.equals("null")) {
            return null;
        }

        return new TreeNode(Integer.valueOf(val));
    }
Copy the code