In Meta Messenger infrastructure, tree-shaped data may need to be converted into a string for transport and rebuilt later. Implement functions to serialize a binary tree into a string and deserialize that string back into the original tree.
A correct solution must preserve both node values and tree structure, including missing children.
serialize: the root of a binary tree where each node has fields val, left, and rightserialize: a string representation of the treedeserialize: a string produced by serializedeserialize: the reconstructed root nodeUse the string format produced by a level-order traversal with # representing null children and values separated by commas.
Example 1
[1,2,3,null,null,4,5]"1,2,3,#,#,4,5,#,#,#,#"# preserves missing children so the structure can be rebuilt exactly.Example 2
[]""null.0 <= number of nodes <= 10^4-1000 <= Node.val <= 1000deserialize is always valid and was produced by serializeroot = [1,2,3,null,null,4,5]Output"1,2,3,#,#,4,5,#,#,#,#"WhyBreadth-first traversal records every node and every missing child, so the original sparse structure can be reconstructed exactly.root = []Output""WhyAn empty tree has no nodes to encode, so serialization returns an empty string and deserialization returns null.root = [7,3,null,1]Output"7,3,#,1,#,#,#"WhyThe null right child of 7 and the missing children of 1 must be preserved with `#` markers.0 <= number of nodes <= 10^4-1000 <= Node.val <= 1000Input to deserialize is always a valid string produced by serializeTree may be balanced, skewed, or sparsedef serialize_deserialize(root):