Flatten - facebook code lab - 2 practices

July 16, 2016

Given a binary tree, flatten it to a linked list in-place.

Example :
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Note that the left child of all nodes should be NULL.

First practice:  Run time error
https://gist.github.com/jianminchen/5cad1bd01525e58da40bff23ab541fc7

Second practice:   Pass all test cases!
https://gist.github.com/jianminchen/8388016355c3e3a393c71b17d508e79b

         1
        / \
       2   3
          /    
         4       

The above tree is serialized by level order traversal, 1 2 3 -1 -1 4 -1 -1 -1

So, that is the reason in the second practice, line ..., line 12, line 34, line 35, discussion of -1 value.

3. Study the iterative solution - editorial solution in C++:

https://gist.github.com/jianminchen/082118552020666ec5c794d1383b6ae8

4. Study the Java solution -

https://gist.github.com/jianminchen/d9f18909417476f7102b5573173336ca