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

For example, Given

The flattened tree should look like:

s思路： 1. 看起來，是先訪問中間，然后左邊，最后右邊。又是一個PRe-order. 2. 用recursive當然最簡單。左邊flatten，右邊flatten,然后讓root指向flatten后的左邊，讓flatten的左邊的尾節點指向flatten后的右邊。也就是說，在flatten過程中需要知道頭節點和尾節點的指針！ 3. 由于要得到左子樹和右子樹的開頭結尾，所以需要開頭結尾指針從底層得到給上層使用，因此用reference！ 4. 用iterative很有意思，用stack很麻煩，反而不用stack的morris比較方便快捷，由于是pre-order：根左右，傳統的方法，訪問了左邊還要回到根以便訪問右邊，所以必須用stack;morris則是換一個角度來看問題，把樹臨時改變一下結構：在每個root時，先找到左子樹的最右節點，然后讓這個最右節點指向右子樹的第一個節點，這就方便了，等訪問完左子樹，就直接訪問右節點！ z正常情況下使用morris，還需要在建立這個輔助的連接后拆除這個連接以還原樹的本來結構，但這道題就要求改變樹的結構，所以說，用morris剛剛好！