In a Meta interview setting, you may need to send a binary tree between services used by products like Messenger or Instagram. Implement two functions: one to serialize a binary tree into a string, and one to deserialize that string back into the original tree.
Your encoding must preserve both node values and tree structure exactly. Different trees must not produce the same serialized output.
serialize(root): the root node of a binary tree, or nullserialize(root): a stringdeserialize(data): a string produced by serializedeserialize(data): the reconstructed root node, or nullUse the following node shape:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
A valid solution should run in linear time relative to the number of nodes.
Example 1
Input: root = [1,2,3,null,null,4,5]
Output: serialized = "1,2,#,#,3,4,#,#,5,#,#"
Explanation: Preorder traversal with # markers preserves missing children.
Example 2 Input: root = [] Output: serialized = "#" Explanation: An empty tree must still be represented explicitly.
0 <= number of nodes <= 10^4-1000 <= Node.val <= 1000deserialize is guaranteed to come from serializeroot = [1,2,3,null,null,4,5]Output"1,2,#,#,3,4,#,#,5,#,#"WhyPreorder traversal records each node and every missing child, so the tree can be reconstructed uniquely.root = []Output"#"WhyAn empty tree is represented by a single null marker.data = "1,2,#,#,3,4,#,#,5,#,#"Output[1,2,3,null,null,4,5]WhyReading tokens recursively rebuilds the same left and right subtree structure.0 <= number of nodes <= 10^4-1000 <= Node.val <= 1000The tree may be skewed or balancedThe input string for deserialization is always generated by the serializerdef serialize_deserialize(root, data=None):