Serialization of binary trees

Binary tree serialization: before, middle, after, sequential traversal implementation

1. Pre-order traversal method

• When serialized, it is divided into three parts (left -> right) : root node, left subtree, and right subtree
• So deserialization uses queues
• (Generally speaking, restoring a binary tree requires pre-order + middle-order/post-order + middle-order, since node contains information about all nodes, including null Pointers, it can be directly restored.)

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

public void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append("null,");
        return;
    }

    // The position is traversed forward
    sb.append("" + root.val + ",");

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

public TreeNode deserialize(String data) {

    LinkedList<String> nodes = new LinkedList<>();

    for (String node : data.split(",")) {
        nodes.offer(node);
    }

    return deserialize(nodes);
}

public TreeNode deserialize(LinkedList<String> nodes) {
    if (nodes.isEmpty()) {
        return null;
    }

    // The position is traversed forward
    String node = nodes.poll();
    if ("null".equals(node)) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(node));

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

    return root;
}
Copy the code

2. Post-order traversal method

• When serializing a post-traversal, you only need to place the append in the post-traversal location, so the serialization order is changed
• Is divided into three parts (left -> right) : left subtree, right subtree, and root node
• So deserialization uses stacks
• When deserializing, we still get the root node first, then the right subtree, and then the left subtree

public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

public void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append("null,");
        return;
    }

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

    // the position is traversed in order
    sb.append("" + root.val + ",");
}

public TreeNode deserialize(String data) {

    LinkedList<String> nodes = new LinkedList<>();

    for (String node : data.split(",")) {
        nodes.push(node);
    }

    return deserialize(nodes);
}

public TreeNode deserialize(LinkedList<String> nodes) {
    if (nodes.isEmpty()) {
        return null;
    }

    // the position is traversed in order
    String node = nodes.pop();
    if ("null".equals(node)) {
        return null;
    }
    TreeNode root = new TreeNode(Integer.parseInt(node));

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

    return root;
}
Copy the code

3. Middle order traversal method

• We cannot deserialize a string into a binary tree by middle traversal, with the pre-traversal root in the first, post-traversal root in the last, and second-order traversal root in the middle
• But it can be serialized

public void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append("null,");
        return;
    }

    serialize(root.left, sb);
    // The sequence traverses the position
    sb.append("" + root.val + ",");
    serialize(root.right, sb);        
}
Copy the code

4. Sequence traversal method

• Serialization is also traversed in order, using queues to traverse each layer of nodes, and then serialized into a string
• Deserialization also uses queue traversal, because null Pointers are also recorded, so useiRecord the position of the child node, not pipe node is empty, must first get judgment

public String serialize(TreeNode root) {
    if (root == null) {
        return "";
    }

    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while(! queue.isEmpty()) { TreeNode node = queue.poll();if (node == null) {
            sb.append("null,");
            continue;
        }

        sb.append("" + node.val + ",");

        queue.offer(node.left);
        queue.offer(node.right);
    }

    return sb.toString();
}

public TreeNode deserialize(String data) {
    if ("".equals(data) || data.length() == 0) {
        return null;
    }

    String[] nodes = data.split(",");
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    for (int i = 1; i < nodes.length;) {
        // Get the node
        TreeNode node =  queue.poll();

        / / the left subtree
        String left = nodes[i++];
        if ("null".equals(left)) {
            node.left = null;
        } else {
            node.left = new TreeNode(Integer.parseInt(left));
            queue.offer(node.left);
        }

        / / right subtree
        String right = nodes[i++];
        if ("null".equals(right)) {
            node.right = null;
        } else {
            node.right = newTreeNode(Integer.parseInt(right)); queue.offer(node.right); }}return root;
}
Copy the code