Hey, I haven?t been here for a long time. Well, that is normal, sometimes you have time to spread a word for the world, sometimes no. Now I have:)
Since I still want to write about algorithms, I will be posting solutions with descriptions for LeetCode Hard difficulty questions. Why? Because I can.
And today, we will speak about quite simple hard task, called: Serialize and Deserialize Binary Tree.
Frankly saying I am not sure why LeetCode decides that this problem is Hard, from my point of view this is Medium complexity, buuuut. We got what we got.
First of all, let?s look on standard Binary Tree:
Ugly drown not balanced binary tree
What kind of cases we can have for a singe node?
- Node can have left and right leaf
- Node can have only left or only right leaf
- Node is a leaf itself ( no children )
These are the cases we need to cover during our serialization / deserialization method implementation. Let?s think how can we serialize tree, which I draw so ugly? Of course it can be a string:
1, 2, 3, 4, 5, #, #, 6
As you can see, we have two ?#? characters, which are showing null node children ( left and right ) for Node 3. It is done to save structure of the binary tree. We basically saving our nodes in level format. Something, which you are doing during BFS tree traversal.
Now, let?s code our serialization function:
Easy, right? In our serialize function we are creating embedded encode function, which in case of node adds it to array of strings, and in case not ? adds # symbol.
Now, let?s write deserilization function. Obviously it will look same, however will just read characters from array, and create required nodes.
So, we creating children for every node value we found, except cases when we have ?#? symbol.
That is it. See you on the next post 🙂
