Practice/Microsoft/Leetcode 297. Serialize and Deserialize Binary Tree

Leetcode 297. Serialize and Deserialize Binary Tree

CodingMust

Problem

Design and implement a codec (encoder/decoder) system for binary trees. Your task is to create two methods:

1. serialize: Convert a binary tree into a string representation
2. deserialize: Reconstruct the original binary tree from the string representation

The key challenge is ensuring that the serialization format captures all information needed to perfectly reconstruct the tree, including the exact positions of null children. Your implementation must handle any valid binary tree and ensure that deserializing a serialized tree produces an identical tree structure.

Requirements

1. Implement a serialize method that takes a binary tree root and returns a string
2. Implement a deserialize method that takes the string and returns the reconstructed tree root
3. The process must be reversible: deserialize(serialize(tree)) must produce an identical tree
4. Handle null nodes appropriately to preserve tree structure
5. Support trees with node values in the range [-1000, 1000]

Constraints

• The number of nodes in the tree is in the range [0, 10^4]
• Node values are between -1000 and 1000
• Your serialization/deserialization strategy should be efficient
• Expected time complexity: O(n) for both operations where n is the number of nodes
• Expected space complexity: O(n) for the serialized string and recursion/queue space

Examples

Example 1:

` Input: root = [1,2,3,null,null,4,5] Tree structure: 1 /
2 3 /
4 5

Serialization possible output: "1,2,null,null,3,4,null,null,5,null,null" After deserialization: Tree structure matches the original `

Example 2:

Input: root = [] Serialization output: "null" or "" After deserialization: null (empty tree)

Example 3:

` Input: root = [1,2,3,4,5] Tree structure: 1 /
2 3 /
4 5

After serialize then deserialize: Structure is preserved exactly `