Serialize and Deserialize a Binary Tree

Given a binary tree represented by a pre-order traversal string with nodes separated by commas, where None represents a null node, your task is to first deserialize the string into a binary tree and then serialize the binary tree back into a string. The output string should match the normalized serialized representation.

The pre-order traversal serialization is defined as follows:

$$ serialize(\text{root}) = \begin{cases} \text{'None'} & \text{if } \text{root is None} \\ \text{str(root.value)} + "," + serialize(root.left) + "," + serialize(root.right) & \text{otherwise} \end{cases} $$

inputFormat

Input is read from standard input as a single line containing a comma-separated string representing the serialized binary tree in pre-order.

outputFormat

Output to standard output the normalized serialized binary tree string (which is the result of deserializing the input and then serializing it back).## sample

1,2,None,None,3,4,None,None,5,None,None

1,2,None,None,3,4,None,None,5,None,None