Leetcode 297: Serialize and deserialize a binary tree - 2 study cases

May 23, 2016

Problem statement:

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

Study solutions:

1. Study code:
Java Solution:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/297.serialize-and-deserialize-binary-tree.java

C# code:
https://gist.github.com/jianminchen/1f88954d31d1ea7c18a2e5f17ed4ab97

Spent 60 minutes (9:30pm - 10:30pm) to set up a test case, modify code to make it readable, debug the code and then understand the design, code works.
https://gist.github.com/jianminchen/da26aa9dbe2a74ea6f641298e57fd289

Test Case:
Tree diagram:

Tree preorder traversal:
            9   5   1   4  2   3  8  7  6
Index:  0   1   2   3  4   5  6  7  8

So, node 9 is serialized:
step 1:
int[3]{9, 1, 6},
9 is the value of node value,
1 is the left child's index position in List<int[]>, value is 5.
6 is the right child's index position in List<int[]>, value is 8.

The tree is serialized as a string:
"9 1 6 5 2 3 1 -1 -1 4 4 5 2 -1 -1 3 -1 -1 8 -1 7 7 8 -1 6 -1 -1 "

2. Study code:
http://www.cnblogs.com/yrbbest/p/5047035.html

C# practice based on the above blog:  (output limit exceeded - Leetcode Online Judge)
https://gist.github.com/jianminchen/f4d6d81f300a0c7c26cc4bcdbe99b3db

Test case:
Tree: Same tree from 1 - 9

Tree serialization string:
9,5,1,#,#,4,2,#,#,3,#,#,8,#,7,6,#,#,#,

Tree preorder traversal:
            9   5   1   4  2   3  8  7  6
So, the binary tree can not be uniquely identified just by preorder traversal of binary tree - a string, only if it is a complete binary search tree or other special tree. The serialization string does not include all the information needed. The design has flaws.


Questions and Answers:

1. How is the practice?

Answer: Try to get more experience on preorder traversal iterative solution, and see how the preorder traversal helps to solve the problem. Debug the code step by step and then understand the design.

C# code:
https://gist.github.com/jianminchen/da26aa9dbe2a74ea6f641298e57fd289

based on study of code:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/297.serialize-and-deserialize-binary-tree.java

Also, study the design of serialization of binary tree using the following ideas:
1. First, use an array to store a tree node;
           array[0] = value;
           array[1] = li,    // left child index, if null, -1
           array[2] = ri,    // right child index, if null, -1
       
 2. nodes will be added to a list of arrays; then, convert the array list to a string.

Come back later to play more with the solution!

More reading about Leetcode problems and solutions:

1. Read the blog - Amazon SDE II - Leetcode solutions

2. Review Leetcode solutions (2nd practice):
http://www.cnblogs.com/yrbbest/tag/2%E5%88%B7/

3. 3rd practice:
http://www.cnblogs.com/yrbbest/tag/3%E5%88%B7/

Actionable items:

1. Need to warm up the algorithm, code writing; it is hard to write bug-free code under stress.

Fun part:
10 ways to check if the number is power of 2
http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/