This is the 30th day of my participation in the Wenwen Challenge

Topic describes

This is the finger Offer 37 on LeetCode. Serialize the binary tree.

Tag: binary tree, sequence traversal

Serialization is the operation of converting a data structure or object into consecutive bits, which can then be stored in a file or memory, or transferred over the network to another computer environment, where the original data can be reconstructed in the reverse way.

Please design an algorithm to implement binary tree serialization and deserialization. There is no limit to the logic of your sequence/deserialization algorithm, you just need to ensure that a binary tree can be serialized to a string and deserialized to the original tree structure.

Tip: The input and output formats are the same as LeetCode currently uses, see LeetCode’s Serialized binary tree format for details. You don’t have to go this way, you can solve the problem in other ways.

Example 1:

Input: root = [1, 2, 3, null, null, 4, 5) output: [1, 2, 3, null, null, 4, 5)Copy the code

Example 2:

Input: root = [] Output: []Copy the code

Example 3:

Input: root = [1] Output: [1]Copy the code

Example 4:

Input: root = [1,2] output: [2]Copy the code

Tip:

  • The number of nodes in the tree is within the range [0 104][0, 10^4][0 104]
  • -1000 <= Node.val <= 1000

The basic idea

No matter what “traversal mode” is used for binary tree storage, we need to have representation of empty nodes for convenience.

In fact, the sample of the topic itself provides us with a good idea: use the way of sequential traversal to store the empty node of a leaf node, and ensure that the corresponding children of the empty node are not stored recursively.

Sequence traversal

According to the data range of the Node value -1000 <= node. val <= 1000 (I was in 297. Binary tree serialization and deserialization look, you can also do not use numbers, use a special character, as long as the anti-sequence is distinguishable), we can create a placeholder node emptyNode to represent the emptyNode (emptynode. val = INF).

Serialization: The empty tree case is excluded first, followed by the normal sequence traversal logic:

  1. At the beginning, I’m going torootNode joining;
  2. Remove the node from the queue and check if the node has left/right nodes:
    • If so, append the value to the serialized character (note the use of delimiters) and enqueue the node;
    • If no, check whether the current node isemptyNodeNode, if notemptyNodeNote It is a common leaf node, and its corresponding empty node needs to be storedemptyNodeThe team;
  3. Loop through process 222 until the entire queue is empty.

Antisequence: In the same way, “serialize” can be “antisequence” :

  1. At the beginning, constructrootIncorporated into the team;
  2. Each time an element is fetched from the queue, two values (corresponding to the left and right nodes) are intercepted from the serialization character and checked forINF, if not toINFThen the corresponding node is constructed.
  3. Loop through process 222 until the entire serialized string is processed (note that the last delimiter is skipped).

Code:

public class Codec {
    int INF = -2000;
    TreeNode emptyNode = new TreeNode(INF);
    public String serialize(TreeNode root) {
        if (root == null) return "";

        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while(! d.isEmpty()) { TreeNode poll = d.pollFirst(); sb.append(poll.val +"_");
            if(! poll.equals(emptyNode)) { d.addLast(poll.left ! =null? poll.left : emptyNode); d.addLast(poll.right ! =null? poll.right : emptyNode); }}return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.equals("")) return null;

        String[] ss = data.split("_");
        int n = ss.length;
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        for (int i = 1; i < n - 1; i += 2) {
            TreeNode poll = d.pollFirst();
            int a = Integer.parseInt(ss[i]), b = Integer.parseInt(ss[i + 1]);
            if(a ! = INF) { poll.left =new TreeNode(a);
                d.addLast(poll.left);
            }
            if(b ! = INF) { poll.right =newTreeNode(b); d.addLast(poll.right); }}returnroot; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is the first Offer of 37 articles in our series of “Brush through LeetCode”. The series started on January 21, 01/01, and there are 1916 questions in LeetCode by the start date, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.