297. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

There may be two perspectives to serialize/deserialize a tree: 1). show the clear range/boundary of each section (left, mid, right), 2). keep the details and small hints of the traversal during serialization.

Using option 1: show the clear range/boundary of each section

IMO, this is the macro-way to resolve this problem. For example, 

   1

  /  \

2     3

We can log the level(depth) information as indicator of the structure. e.g. "(2) 1 (3)". During serialization, the range of each subtree can be kept.

• Pros: of this approach is it applies to all of pre-order, in-order and post-order serialization.
• Cons: needs more data to log range information, and requires look-back during deserialization.

Using option 2: keep details of traversal

With this option, it is unlikely that a human can know the structure of the tree clearly through a glance of the serialized data. However, the algorithm itself should be smart enough to reconstruct the tree piece by piece.

If using pre-order, we can serialize like this. "2,up,1,right,left,4,up,3,down,5,up,up"

If using in-order, we can serialize like this. "1,2,null,null,3,null,null". Although the range is not straightforward itself, the traversal will reveal the boundary by checking the end (leaf node)  of each subtree.

• Pros: with careful design, save the size of serialized data. 
• Cons: need further caution to avoid ambiguity in interpreting data especially for similar but different subtree, or whether it goes to parent node or sibling node.