Leetcode 114: Flatten binary tree to linked list - Every road leads to Rome

July 26, 2018

Introduction

It is most famous verse "Every road leads to Rome", and I learn from my mock interview experience. Every peer solves binary tree problem different ways, I have met over 100 people to work on binary tree. But every road leads to Rome. I have to be open to ideas, and make every idea work in my practice as well.

Story begins this way

Idea A -> failed a few times over 30 minutes -> Idea B -> succeed in less than five minutes using idea B-> felt happy over 30 minutes -> feel not right -> go back to idea A, and try to make it work. Less stress -> really learning begins here

Idea A -  left subtree as a linked list, which should connect to right subtree as linked list.
Idea B - using two global variable, previousNode, currentNode.


It is a medium level tree algorithm. I spent more than two hours to work on the algorithm tonight. I could not make the idea work more than 30 minutes, I try to make the left subtree's last node connect to the right child. I knew that my code was too complicated.

I have tried all possible solutions in the first hour, I could not make it work. And then I solved the algorithm using two global variables - previousNode, currentNode first. After 20 minutes, I decided to go back to original idea, and I felt so relaxed. I like to make my original idea work as well.

Here is the submission records. Tonight at least I struggled more than 20 minutes on this idea until I tried to write simple code, changed the idea to use two global variables, 1 hour, 37 minutes ago with one succeed submission. Now it is 10:55 PM, 10:30 I submit a solution and passed online judge using the original idea.

My submissions of Leetcode 114

Here is my solution submitted on June, 2016. I need to review the solution again.

Here is my solution which passes Leetcode online judge, submitted in July 25, 2018 at 9:10 PM. The idea is to use two global variables.

Here is my solution which passes Leetcode online judge, submitted in July 25, 2018 at 10:30 PM. The idea is to find left subtree's last node, and make it connected to right subtree linked list.

Follow up 

7/28/2018 9:11 AM
I like to show the image to compare two submission, left side is the problematic code, right side is the code which passes online judge. How to think and solve the problem?

I am trying to write down some notes here to coach myself, next time I should be careful.

First, choose the preorder traversal. Visit root node first, and then recursive call of root.left and root.right. Here when the root node is visited, assign root variable to the global variable currentNode on line 11.

Next, I need to find the place when the currentNode is the last node of left subtree, and then I need to set it next point to right subtree linked list's first node. Here line 15 I put comment saying currentNode is the last node in left subtree.