297. Serialize and Deserialize Binary Tree

Published on August 7, 2023

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Algorithm

This question is an open question and have many ways to implement, I only give one of mine, it may not be the best but it's easy to come up.

Basically my way is utilizing the level order traversal. For serialize, we traverse the tree level by level and record the nodes value including null. For deserialize, we construct the tree level by level, by using the index relationship of the binary tree.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    final String DELE = ",";
    final String NULL = "#";
    String data = "";
    Queue<TreeNode> list = new LinkedList<>();
    

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return NULL;
        list.add(root);
        data = String.valueOf(root.val);
        while (!list.isEmpty()) {
            TreeNode node = list.poll();
            if (node.left == null) {
                data = data + DELE + NULL;
            } else {
                data = data + DELE + String.valueOf(node.left.val);
                list.offer(node.left);
            }
            if (node.right == null) {
                data = data + DELE + NULL;
            } else {
                data = data + DELE + String.valueOf(node.right.val);
                list.offer(node.right);
            }
        }
        return data;
    }
    
    

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (NULL.equals(data)) return null;
        
        String[] nodes = data.split(",");
        TreeNode root = new TreeNode(Integer.valueOf(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 0;
        while (!queue.isEmpty() && i < nodes.length) {
            TreeNode node = queue.poll();
            if (!NULL.equals(nodes[2*i+1])) {
                node.left = new TreeNode(Integer.valueOf(nodes[2*i+1]));
                queue.offer(node.left);
            }
            if (!NULL.equals(nodes[2*i+2])) {
                node.right = new TreeNode(Integer.valueOf(nodes[2*i+2]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));