0114. Flatten Binary Tree to Linked List (Medium)

Question

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

For example, given the following tree:

1
2
3
4
5

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

分析/解題

給定一個二元樹，請將其攤平成linkedlist形式且以in-place的條件進行。
依照題目要求攤平後，整棵樹應該會變成每一個節點只會有右邊的節點。

仔細觀察題目我們會發現其走訪的順序其實是pre-order。(中左右)
那麼，該怎麼做到攤平呢？

我們可以先考慮某個子樹的情況，
根節點自己在攤平後應該還是不會動，
而所有左子樹的節點在攤平後應該都排在右子樹節點的前面 。
所以當我們假定先完成了一個樹的左右子樹的攤平的話，
樹應該長得像這樣：

1
2
3
4
5
6
7

　 a
 /  \
b    e
 \    \
  c    f
   \    \
    d    g

那麼，我們要做的應該是將d跟e接起來(a-e斷開) ，
並且將b的位置從a的左邊挪到右邊 。

所以整個流程會像這樣：

1. 檢查根節點 ，是NIL則回傳(代表這條路走到底了)。
2. 先記錄左右節點備用(l, r)，
   並分別呼叫自己的左右節點進入flatten遞迴 。
3. 經過2以後左右子樹應該分別攤平了，
   現在將左節點設為null，右節點設為l 。
4. 使用迴圈找到root.right的最右邊的節點 (也就是原先左子樹的最後一個節點)，
   將其和r接起來。(也就是在做上圖的d跟e 的銜接)

Java

Python

讀者可能會注意到上面也提供了迭代解，
這個版本的解法源自於Morris Traversal ，
有興趣的讀者可以了解一下。

簡單來說呢，它做的事情跟遞迴是一致的，
不過它不需要使用到call stack，
只需要用到輔助的TreeNode 來記錄先前的root.right。
每次我們會檢查左節點是否為NIL ，
是的話我們可以直接往右邊走 (因為左邊不用處理了)；
接著做的事情相同，先用tmp暫時存下右子樹 ，
對左子樹進行接到右邊的動作。 (也就是每一次會處理掉每個左子樹的右邊的分枝 )
這整個流程並不是很好理解，
讀者只需留意到其時間複雜度一樣是O(N) 即可，
在實際面對類似題目時，如果沒有把握，可以以前面的遞迴解為主。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，但遞迴解的空間複雜度要另行考慮call stack，
若平衡的話是O(logN))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~