Sweaty Imposter

Serialize and Deserialize Binary Tree

HardTree BFSBlind 75SeniorOpen on LeetCodeUpdated

Design a codec for binary trees. serialize(root) turns a tree into a string, and deserialize(data) rebuilds the same tree from that string, with the same shape and the same value in every position. The format is yours to choose. Node values can be negative, and the tree can be empty.

Examples

root = [7,3,9,null,4] returns [7,3,9,null,4]

7394

A level-order encoding with # for missing children writes this tree as "7,3,9,#,4,#,#,#,#". Decoding reads it back into the same shape.

root = [] returns []

An empty tree serializes to an empty string and comes back as null.

root = [-5,null,-5] returns [-5,null,-5]

Values repeat and are negative, and the only child is on the right. The null markers keep that child from moving to the left side.

Constraints

  • 0 <= number of nodes <= 10^4
  • -1000 <= Node.val <= 1000

Hints

Hint 1

A list of values alone loses information. What do you need to record so a left child and a right child can't be confused?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Walk the tree level by level with a queue and write every node's value, writing # for each missing child, separated by commas. To rebuild, read the first token as the root and push it onto a queue. For each node you pop, the next two tokens are its left and right children: create a node for each value and push it, or leave the child null for #. The null markers pin down the shape exactly, and the iterative walk avoids deep recursion on a skewed tree. O(n) time and space in both directions.

Time

O(n)

Space

O(n)

Pitfall

Leaving out null markers, or writing only one traversal. A preorder list of values alone can't tell a left child from a right child, so [1,2] and [1,null,2] encode the same way.

Solutions

public class Codec {
    public String serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("#,");
                continue;
            }
            sb.append(node.val).append(',');
            queue.add(node.left);
            queue.add(node.right);
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        String[] tokens = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(tokens[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!tokens[i].equals("#")) {
                node.left = new TreeNode(Integer.parseInt(tokens[i]));
                queue.add(node.left);
            }
            i++;
            if (!tokens[i].equals("#")) {
                node.right = new TreeNode(Integer.parseInt(tokens[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}
Drill This