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

For example, Given

The flattened tree should look like:

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