2021-06-30 LeetCode problem of the Day

Link: leetcode-cn.com/problems/xu…

Tags: tree, depth-first search, breadth-first search, design, string, binary tree

The title

Implement two functions to serialize and deserialize the binary tree.

You need to 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.

Enter: root = [1.2.3.null.null.4.5] output: [1.2.3.null.null.4.5]
Copy the code

Analysis of the

If you want to build a tree, a tree can be identified by pre-order traversal and mid-order traversal, and a tree can be identified by mid-order traversal and subsequent traversal.

So we can get the pre-order and middle-order traversal of the binary tree first (or middle-order traversal and subsequent traversal) and return it as a string. The string is then converted into two sequences from which the binary tree is reconstructed. It’s a little tedious to do.

As you can see, the input given in the example is sequence traversal, so we can get the sequence traversal of the tree through BFS, and then restore the binary tree through the result of the sequence traversal. Based on the output from the example, we only need to make the tree a full binary tree (i.e., fill the left subtree and then the right subtree), so we need to set the left subtree to null.

The example tree looks like this

coding

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(! queue.isEmpty()) {int len = queue.size();
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                // append the comma directly, so that when split, the end of the null character will be removed
                // for the example, the resulting strings are 1,2,3, 4,5,,,,
                / / after the split segmentation, get a string array (" 1 ", "2", "3", ""," ", "4", "5"]
                if (node == null) {
                    sb.append(",");
                } else {
                    sb.append(node.val).append(","); queue.offer(node.left); queue.offer(node.right); }}}return sb.substring(0, sb.length() - 1).toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<TreeNode> queue = new LinkedList<>();
        String[] vals = data.split(",");
        TreeNode root = (!"".equals(vals[0))? (new TreeNode(Integer.parseInt(vals[0))) :null;
        TreeNode node = root;
        queue.offer(node);
        int index = 1;
        while(! queue.isEmpty() && index < vals.length) {int len = queue.size();
            for (int i = 0; i < len && index < vals.length; i++) {
                TreeNode temp = queue.poll();
                if (temp == null) {
                    continue;
                }
     
                String str = vals[index++];
                temp.left = !"".equals(str) ? new TreeNode(Integer.parseInt(str)) : null;
                if (index >= vals.length) {
                    break;
                }
                str = vals[index++];
                temp.right = !"".equals(str) ? new TreeNode(Integer.parseInt(str)) : null; queue.offer(temp.left); queue.offer(temp.right); }}returnroot; }}// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
Copy the code