CIn a Meta-style systems setting such as caching tree-structured ranking features for Facebook Feed, you may need to convert a binary tree into a compact string and later rebuild the exact same tree. Implement both serialization and deserialization.
Given the root of a binary tree, write two functions:
serialize(root) that converts the tree into a string.deserialize(data) that reconstructs the original binary tree from that string.Your encoding must preserve both node values and structure, including missing children.
serialize: root, the root node of a binary tree or nullserialize: a string representation of the treedeserialize: data, a string produced by serializedeserialize: the reconstructed root node or nullYou may choose any deterministic format, but deserialize(serialize(root)) must produce a tree identical to the original.
Example 1
root = [1,2,3,null,null,4,5]"1,2,#,#,3,4,#,#,5,#,#"# markers preserves missing children.Example 2
root = []"#"[0, 10^4]-1000 <= Node.val <= 1000root = [1,2,3,null,null,4,5]Output"1,2,#,#,3,4,#,#,5,#,#"WhyPreorder records each node and each missing child, so the exact original structure can be reconstructed.root = []Output"#"WhyAn empty tree has no nodes, so a single null marker is sufficient.root = [7,-3,null,null,9]Output"7,-3,#,#,9,#,#"WhyNegative values are serialized as normal tokens, and null children are still represented explicitly.The number of nodes is in the range [0, 10^4]-1000 <= Node.val <= 1000The tree may be emptyThe tree may be highly unbalanceddeserialize must correctly reconstruct any string produced by serializedef serialize_deserialize_tree(root):