preface

Recently, I am looking at the algorithm, which needs to be picked up from time to time so that I can think and update my knowledge base.

This article mainly includes two solutions:

  • The former sequence traversal
  • After the sequence traversal

As for why middle traversal can’t, you’ll see at the end.

Preorder traversal serialization and deserialization

Train of thought

The binary tree structure is serialized into a string by sequential traversal, with empty nodes represented by #. In deserialization, queue is used to store all nodes (according to the sequential traversal order storage), judge whether the current queue element is #, if so, it is an empty node, if not, a new tree node is created, and process the left and right subtrees of the node successively.

code

public class Main {

    /** * serialization -> implementation of sequential traversal -> root left/right */
    public String serialize(TreeNode root) {
        if(root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    /** * deserialize -> implement with sequential traversal -> root left/right */
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList(Arrays.asList(data.split(",")));
        return deserialize(queue);
    }
    
    private TreeNode deserialize(Queue<String> queue) {
    	if (queue.isEmpty()) return null;
        String cur = queue.pop();
        if(cur.equals("#")) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(cur)); // Create a node
        node.left = deserialize(queue); / / the left subtree
        node.right = deserialize(queue); / / right subtree
        returnnode; }}Copy the code

Postsequential traversal serialization and deserialization

Train of thought

Subsequent traversal serializes the binary tree structure into a string, with empty nodes represented by #. The stack is queued first and then out, that is, the left and right subtrees and root nodes added first during serialization will be built in the same order as the queue used in previous traversal after data is stored in the stack. In deserialization, stack is used to store all nodes (according to the storage sequence of subsequent traversal), judge whether the current queue element is #, if so, it is an empty node, if not, a new tree node is created, and process the left and right subtrees of the node successively.

code

public class Main {

    /** * serialization -> implementation of sequential traversal -> root left/right */
    public String serialize(TreeNode root) {
        if(root == null) return "#";
        return serialize(root.left) + "," + serialize(root.right) + "," + root.val;
    }

    /** * deserialize -> implement with sequential traversal -> root left/right */
    public TreeNode deserialize(String data) {
    	Stack<String> stack = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserialize(stack);
    }
    
    private TreeNode deserialize(Stack<String> stack) {
    	if (stack.isEmpty()) return null;
        String cur = stack.pop();
        if(cur.equals("#")) return null;
        
        TreeNode node = new TreeNode(Integer.parseInt(cur)); // Create a node
        node.left = deserialize(stack); / / the left subtree
        node.right = deserialize(stack); / / right subtree
        returnnode; }}Copy the code

Sequential traversal serialization and deserialization

It can be found that the binary tree serialization and deserialization cannot be completed because the root node cannot be found in the middle traversal first.

Rebuild the binary tree

Rebuilding a binary tree by traversing a sequence of anteorders and a sequence of mid-orders sounds impressive, but the reason I’m writing it here is because I think it’s important.

Train of thought

By serializing and deserializing the binary tree above, we see that it is important to find the root node first when rebuilding the binary tree. (This is consistent with the idea of deserialization of binary tree) So we can find the root node through sequential traversal first, and then according to the known root node in the middle traversal, we can get the coordinate positions of the corresponding left subtree node array, right subtree node array and root node in the middle traversal respectively. Good, so we can find the root node, the left subtree, and the right subtree on the first call. The last step is a recursive call, which takes the left node of the root node and the right node of the root node as the parent node to find their corresponding subtrees respectively.

code

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if (pre == null || pre.length == 0) {
        return null;
    }
    int pos = 0, len = pre.length, val = pre[0];
    for(; pos < len; pos++) {if (in[pos] == val) {
            break;
        }
    }
    TreeNode root = new TreeNode(val);
    // Divide the corresponding array according to the preceding and middle traversal rules to obtain the left and right subtrees
    root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, pos+1), Arrays.copyOfRange(in, 0, pos)); / / the left subtree
    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, pos+1, len), Arrays.copyOfRange(in, pos+1, len)); / / right subtree
    return root;
}
Copy the code

Through the idea of rebuilding the binary tree, it also reflects why the middle order traversal can not complete the deserialization operation of the binary tree.

conclusion

These days, I have done a lot of algorithm problems related to trees. It is summarized that on the basis of familiar traversal methods, some queues and stacks are added to ensure the sequence of nodes, so that most of the algorithm problems can be completed.

Personal note

The contents of this blog are all notes made by the author to learn, invade and delete! If used for other purposes, please specify the source!