Serialize and Deserialize a Binary Tree

Design an algorithm to serialize a binary tree into a single string, and deserialize that string back into a binary tree with the exact same structure and values as the original.

There is no constraint on how your serialization format must look, as long as a tree can be serialized to a string and that string deserialized back to a tree that is structurally identical to the original (same shape, same values, including the placement of null children).

Implement two functions:

• serialize(root) -> str
• deserialize(data: str) -> TreeNode

Example 1

Input tree: [1, 2, 3, null, null, 4, 5]

      1
     / \
    2   3
       / \
      4   5

serialize(root) might produce something like "1,2,#,#,3,4,#,#,5,#,#" (preorder with # marking nulls); deserialize on that string must reconstruct the identical tree.

Example 2

Input tree: [] → serialize produces some representation of an empty tree (e.g. "#"), and deserialize on that returns None.

Constraints

• The number of nodes is in the range [0, 10^4].
• -1000 <= Node.val <= 1000.