Binary tree (serialization)

JSON It's widely used , For example, we often sequence the structure of a language into JSON character string , It's stored in a cache or sent to a remote service over the network , Consumer acceptance JSON The string is then deserialized , You can get the raw data . This is it. 「 serialize 」 and 「 Deserialization 」 Purpose , Organize strings in some fixed format , Make data independent of programming language .

This article will use the preface 、 Middle preface 、 Post order traversal to serialize and deserialize binary trees , further , We will also use iterative hierarchical traversal to solve this problem .

One 、 Title Description

Force to buckle 297 topic 「 Serialization and deserialization of binary trees 」

Is to input the root node of a binary tree for you root, You are required to implement the following class ：

public class Codec {
    

    //  Sequence a binary tree into a string 
    public String serialize(TreeNode root) {
    }

    //  Deserialize a string into a binary tree 
    public TreeNode deserialize(String data) {
    }
}

Two 、 Preorder traversal solution

Imagine , The binary tree junction should be a two-dimensional structure in the plane , And the serialized string is a linear one-dimensional structure . The so-called serialization is just the structured data 「 Strike a level 」, In fact, it is to investigate the traversal way of binary tree .

StringBuilder Can be used to efficiently concatenate strings , So it's also a list , use , As a separator , use # Represents a null pointer null

thus , We've been able to write serialization functions serialize The code of ：

String SEP = ",";
String NULL = "#";

/*  The main function , Serialize a binary tree into a string  */
String serialize(TreeNode root) {
    
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

/*  Auxiliary function , Store the binary tree in  StringBuilder */
void serialize(TreeNode root, StringBuilder sb) {
    
    if (root == null) {
    
        sb.append(NULL).append(SEP);
        return;
    }

    /******  Preorder traversal position  ******/
    sb.append(root.val).append(SEP);
    /***********************/

    serialize(root.left, sb);
    serialize(root.right, sb);
}

Think about how to write it deserialize function , Reverse the string to construct a binary tree .

In the general context , The result of preorder traversal alone cannot restore the binary tree structure , Because of the lack of null pointer information , At least get before 、 in 、 In order to restore the binary tree, two kinds of post order traversal can be used . But here node The list contains information about null pointers , So just use node List can restore the binary tree .

that , The same is true for deserialization , First determine the root node root, Then follow the rules of preorder traversal , The left and right subtrees are generated recursively ：

/*  The main function , Deserialize a string into a binary tree structure  */
TreeNode deserialize(String data) {
    
    //  Convert string to list 
    LinkedList<String> nodes = new LinkedList<>();
    for (String s : data.split(SEP)) {
    
        nodes.addLast(s);
    }
    return deserialize(nodes);
}

/*  Auxiliary function , adopt  nodes  List construction binary tree  */
TreeNode deserialize(LinkedList<String> nodes) {
    
    if (nodes.isEmpty()) return null;

    /******  Preorder traversal position  ******/
    //  At the far left of the list is the root node 
    String first = nodes.removeFirst();
    if (first.equals(NULL)) return null;
    TreeNode root = new TreeNode(Integer.parseInt(first));
    /***********************/

    root.left = deserialize(nodes);
    root.right = deserialize(nodes);

    return root;
}

3、 ... and 、 Post order ergodic solution

Understand the solution of preorder traversal , Post order traversal is easier to understand , Let's first achieve serialize Serialization method , You can just modify the method a little ：

/*  Auxiliary function , Store the binary tree in  StringBuilder */
void serialize(TreeNode root, StringBuilder sb) {
    
    if (root == null) {
    
        sb.append(NULL).append(SEP);
        return;
    }

    serialize(root.left, sb);
    serialize(root.right, sb);

    /******  Postorder traversal position  ******/
    sb.append(root.val).append(SEP);
    /***********************/
}

deserialize Methods first look for root The value of the node , Then recursively calculate the left and right child nodes

so ,root The value of is the last element of the list . We should take the list elements from back to front , Construct with the last element first root, And then recursively call to generate root Right and left subtrees . Be careful , According to the picture above , From back to front in nodes Take the elements from the list , Make sure to construct first root.right subtree , Post structure root.left subtree .

/*  The main function , Deserialize a string into a binary tree structure  */
TreeNode deserialize(String data) {
    
    LinkedList<String> nodes = new LinkedList<>();
    for (String s : data.split(SEP)) {
    
        nodes.addLast(s);
    }
    return deserialize(nodes);
}

/*  Auxiliary function , adopt  nodes  List construction binary tree  */
TreeNode deserialize(LinkedList<String> nodes) {
    
    if (nodes.isEmpty()) return null;
    //  Take the elements from back to front 
    String last = nodes.removeLast();
    if (last.equals(NULL)) return null;
    TreeNode root = new TreeNode(Integer.parseInt(last));
    //  Restricted construction right subtree , The left subtree is constructed after 
    root.right = deserialize(nodes);
    root.left = deserialize(nodes);

    return root;
}

Four 、 Middle order ergodic solution

Say first conclusion , Middle order traversal doesn't work , Because the deserialization method cannot be implemented deserialize. Middle order traversal code ,root The value of is sandwiched between two subtrees , That is to say nodes In the middle of the list , We don't know the exact index location , So we can't find root node , You can't deserialize .

5、 ... and 、 Hierarchical ergodic solution

First , First write the code framework of traversing the binary tree hierarchically ：

void traverse(TreeNode root) {
    
    if (root == null) return;
    //  Initialize queue , take  root  Join the queue 
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
    
        TreeNode cur = q.poll();

        /*  Level traversal code location  */
        System.out.println(root.val);
        /*****************/

        if (cur.left != null) {
    
            q.offer(cur.left);
        }

        if (cur.right != null) {
    
            q.offer(cur.right);
        }
    }
}

The above code is a standard binary tree level traversal framework , From top to bottom , Print the values of each level of binary tree nodes from left to right , You can see , queue q There won't be null The pointer .

However, we need to record null pointer in the process of deserialization null Of , So the standard hierarchical traversal framework can be slightly modified

String SEP = ",";
String NULL = "#";

/*  Serialize a binary tree into a string  */
String serialize(TreeNode root) {
    
    if (root == null) return "";
    StringBuilder sb = new StringBuilder();
    //  Initialize queue , take  root  Join the queue 
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    while (!q.isEmpty()) {
    
        TreeNode cur = q.poll();

        /*  Level traversal code location  */
        if (cur == null) {
    
            sb.append(NULL).append(SEP);
            continue;
        }
        sb.append(cur.val).append(SEP);
        /*****************/

        q.offer(cur.left);
        q.offer(cur.right);
    }

    return sb.toString();
}

You can see , Each non empty node corresponds to two child nodes , So the idea of deserialization is to traverse hierarchically with queues , At the same time, index i Record the location of the corresponding child node ：

/*  Deserialize a string into a binary tree structure  */
TreeNode deserialize(String data) {
    
    if (data.isEmpty()) return null;
    String[] nodes = data.split(SEP);
    //  The first element is  root  Value 
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));

    //  queue  q  Record parent , take  root  Join the queue 
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    for (int i = 1; i < nodes.length; ) {
    
        //  There are all parent nodes in the queue 
        TreeNode parent = q.poll();
        //  The value of the left child node corresponding to the parent node 
        String left = nodes[i++];
        if (!left.equals(NULL)) {
    
            parent.left = new TreeNode(Integer.parseInt(left));
            q.offer(parent.left);
        } else {
    
            parent.left = null;
        }
        //  The value of the right child node corresponding to the parent node 
        String right = nodes[i++];
        if (!right.equals(NULL)) {
    
            parent.right = new TreeNode(Integer.parseInt(right));
            q.offer(parent.right);
        } else {
    
            parent.right = null;
        }
    }
    return root;
}

This code can test your framework thinking . Take a close look at for Loop part of the code , Found that this is not the standard level traversal code derived from it ：

while (!q.isEmpty()) {
    
    TreeNode cur = q.poll();

    if (cur.left != null) {
    
        q.offer(cur.left);
    }

    if (cur.right != null) {
    
        q.offer(cur.right);
    }
}

It's just , The standard level traversal operates on binary tree nodes TreeNode, And our functions operate nodes[i], This is exactly the purpose of deserialization .