preface

Binary tree serialization and deserialization, I use BFS (breadth-first traversal) method to do. In fact, friends also use BFS for job interviews.

Serialization and deserialization of binary trees

The running result of BFS is not very satisfactory, so I used DFS (depth-first traversal) to do it again today. The time comparison of the two methods:

As you can see, DFS is much faster than BFS, so share the solution of DFS.

The title

Let’s take a look at the title:

The former sequence traversal

I don’t need to go into details here, but go directly to the code:

private void ser(StringBuilder sb, TreeNode root) {
    if (root == null) {
        sb.append("nil,");
        return;
    }
    sb.append(root.val).append(",");
    ser(sb, root.left);
    ser(sb, root.right);
}

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    ser(sb, root);
    return sb.substring(0, sb.length() - 1);
}
Copy the code

So if you get a null case here, you have to concatenate the result to nil, so that when you reconstruct the binary tree you know which nodes don’t have left and right children.

deserialization

Serialize the tree given by the title:

Pre-order traversal is root first, then left and right. So when rebuilding, it is also from the root to the left and right:

  1. Build (1) // Root node
  2. Start thinking about root’s left child: Build (2)
  3. Start thinking about the left child of 2: build(nil) // If it hits nil, it’s gone. And then the right child of 2 is nil. That’s where the path ends
  4. After considering the left child of root, start considering the right child of root: build(3)
  5. Then consider the left child of 3: build(4); 3 right child: Build (5)
  6. And so on.

To put it bluntly, the recursive process is the same as the previous iteration.

So go straight to the code and feel it:

private TreeNode des(LinkedList<String> strings) {
    // Take each element in turn
    String poll = strings.poll();
    // If there is none or nil, return null
    if (poll == null || "nil".equals(poll)) {
        return null;
    }
    // Build the current node
    TreeNode root = new TreeNode(Integer.parseInt(poll));
    // Build the left child of the current node
    root.left = des(strings);
    // Build the right child of the current node
    root.right = des(strings);
    // Return the current node. (When returned, it becomes the left or right child of its previous node/or is itself the root node)
    return root;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data == null || data.isEmpty()) {
        return null;
    }
    LinkedList<String> strings = new LinkedList<>(Arrays.asList(data.split(",")));
    return des(strings);
}
Copy the code

conclusion

Recursion is an abstract thing, and it’s hard to explain in detail. So for this approach, or need to be more thoughtful. Well, next time, I won’t do it, hahaha~~~

Declined reprint

【Happyjava】 original article, without permission, declined to be reproduced!