Back to DSA

Serialize and Deserialize Binary Tree

hard
Acceptance: 44%
Binary Tree

Construct an algorithm that converts a binary tree into a string representation and another that reconstructs the original tree from that string. The format of the string is your design choice, but the round-trip must be lossless.

Examples

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

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyValidate Binary Search TreemediumLowest Common Ancestor of a Binary TreemediumBinary Tree Level Order Traversalmedium
00:00
import java.util.*;

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

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

    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(",")));
        return desHelper(queue);
    }

    private TreeNode desHelper(Queue<String> queue) {
        String val = queue.poll();
        if ("null".equals(val)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = desHelper(queue);
        node.right = desHelper(queue);
        return node;
    }
}
Time complexityO(n)
Space complexityO(n)