[Tree] Flatten Binary Tree to Linked List

트리가 주어지면 이를 Linked-List로 바꾸는 문제이다.

조건에 따라 right node는 next node가 되고, previous는 null이 된다.

 

convertToList라는 함수를 제외하고 보자.

Tree니까 재귀를 떠올리고.

root가 주어지면, root의 left와 right를 flat하게 만든 후, null- root - left subtree - right subtree 형태로 붙이면된다.

이때 left와 right의 관계를 재귀로 처리해준다.

 

이제 convertToList를 살펴보면, right가 있는 경우, left.right가 null이 될대까지 모든 left node를 거슬러 내려간다

예컨데 left의 node가 3개라면, first.right는 Loop가 세번 돌아야 존재할것이다.

그렇게 left의 마지막 노드를 찾으면, 비로소 first.right에 right subtree를 붙여준다