1 題目描述

簡單來說就是要把一個二元樹轉換成一個只有右子樹的鏈表。變成linkedlist。並且題目特別要求，使用 in-place 的方式。

2 解法

2.1 DFS

一開始你會發現基本上他就是DFS，依序走訪每個節點，然後把每個節點的左子樹接到右子樹，然後把左子樹設為空。
題目中，要求說是in-place，也就是說in-place 的意思可能更多說的是直接在原來的節點上改變指向，空間複雜度並沒有要求。所以這題也可以用遞迴解一下，這時候會讓我們想到DFS preorder的做法。詳細可以參考這篇LeetCode 課前預習 - 掌握 BFS 與 DFS 指南。

但是你在推導的時候會發現：

1
2
3
4
5
6
7

    1
   / \
  2   5
 / \   \
3   4   6

preorder: 1 -> 2 -> 3 -> 4 -> 5 -> 6 

我們知道題目給定的遍歷順序其實就是preorder遍歷的順序，所以我們能不能利用preorder遍歷的程式碼，每遍歷一個節點，就將上一個節點的右邊指標更新為目前節點。
preorder遍歷的順序是1 2 3 4 5 6。

• 遍歷到2，把1的右指針指向2。1 -> 2 3 4 5 6。
• 遍歷到3，把2的右指針指向3。1 -> 2 -> 3 4 5 6。
• …

但是現實是殘酷的，如果我們把 1.right 指向 2，那原本的 1的右子樹就會消失，所以我們需要一個變數來記錄原本的右子樹。或是說，我們可以先從右子樹下手，先處理好最右邊的子樹，慢慢往左處理，那就不會有右子樹丟失的問題了？

解決方法的話，我們可以逆過來進行
我們依序遍歷6 5 4 3 2 1，然後每遍歷一個節點就將目前節點的右指標更新為上一個節點。

• 遍歷到5，把5的右指針指向6。6 <- 5 4 3 2 1。
• 遍歷到4，把4的右指針指向5。6 <- 5 <- 4 3 2 1。
• …

那這個逆過來的順序是 postorder，只是順序是 右子樹->左子樹->根節點，所以我們可以用遞迴的方式來解這題。這樣就不會有丟失孩子的問題了，因為更新目前的右指標的時候，目前節點的右孩子已經訪問過了。

而6 5 4 3 2 1的遍歷順序其實變形的後序遍歷，遍歷順序是右子樹->左子樹->根節點。

先回想一下變形的postorder遍歷的程式碼

1
2
3
4
5
6
7
8
9

def postorder_traversal(root):
    def postorder(node):
        if not node:
            return 
        postorder(node.right)
        postorder(node.left)
        print(node.val)
    
    postorder(root)

然後我們修改一下要把最底慢慢串上去

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    pre = None
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return
        self.flatten(root.right)
        self.flatten(root.left)
        root.right = self.pre
        root.left = None
        self.pre = root

2.2 Morris Traversal

另一個作法是，如果我們想要實現 O(1) 的空間複雜度，那我們可以使用Morris Traversal，簡單來說他就是不斷地

1. 把右子樹接到左子樹的最右邊
2. 然後把左子樹接到右子樹
3. 然後把左子樹設為空。

這樣就可以達到題目的要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

// 先找到cur.左子樹的最右邊節點 rightmost (4)
    1 <--- cur 
   / \
  2   5  <--- cur.right 
 / \   \
3   (4) 6
 
// 先找到cur.left 接到 rightmost.right (4)
    1 <--- cur 
   / 
  2 <--- cur.left  
 / \  
3   (4) <--- rightmost 
      \
       5 <--- cur.right  
        \
         6

// 然後把 cur.left 接到 cur.right
// 設定 cur.left 為空 
    1 <--- cur 
   / \
null  2  <--- cur.right = cur.left           
     / \          
    3  (4)  <--- rightmost 
         \
          5
           \
            6

// 將 cur 移動到 cur.right 
// 重新找到 cur.left 的最右邊節點 rightmost (3)
    1
     \
      2 <--- cur           
     / \          
   (3)  4 <--- cur.left 
         \
          5
           \
            6

// 先找到cur.left 接到 rightmost.right (4)
    1
     \
      2 <--- cur           
     / 
   (3)
     \
      4  <--- cur.left 
       \
        5
         \
          6


// 將 cur.left 接到 cur.right
// cur.left 設為空
    1
     \
      2  <--- cur         
       \          
       (3) <--- cur.left = cur.right      
         \
          4  
           \
            5
             \
              6         
......

那我們來一步步開始實作吧！

1
2
3
4
5
6

// 先找到cur.左子樹的最右邊節點 rightmost (4)
    1 <--- cur 
   / \
  2   5  <--- cur.right 
 / \   \
3   (4) 6

1
2
3
4
5
6

if cur.left:
    # 要找到cur.left的最右邊節點
    rightmost = cur.left 
    # 開始往左子樹的最右邊走
    while rightmost.right:
        rightmost = rightmost.right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// 先找到cur.left 接到 rightmost.right (4)
    1 <--- cur 
   / 
  2 <--- cur.left  
 / \  
3   (4) <--- rightmost 
      \
       5 <--- cur.right  
        \
         6

// 然後把 cur.left 接到 cur.right
// 設定 cur.left 為空 
    1 <--- cur 
   / \
null  2  <--- cur.right = cur.left           
     / \          
    3  (4)  <--- rightmost 
         \
          5
           \
            6

1
2
3

rightmost.right = cur.left
cur.right = cur.left 
cur.left = None

1
2
3
4
5
6
7
8
9
10
11

// 將 cur 移動到 cur.right 
// 重新找到 cur.left 的最右邊節點 rightmost (3)
    1
     \
      2 <--- cur           
     / \          
   (3)  4 <--- cur.left 
         \
          5
           \
            6

1
2
3
4

while cur: 
    step1(...)
    step2(...) 
    cur = cur.right 

把上面三個步驟串起來，就是完整的程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        cur = root
        while cur:
            if cur.left:
                rightmost = cur.left 
                while rightmost.right:
                    rightmost = rightmost.right
                rightmost.right = cur.right
                cur.right = cur.left 
                cur.left = None
            cur = cur.right

3 結語

這題花真的很久的時間，第一次看到Morris Traversal的時候，真的覺得很神奇，直接看code看不懂，還是要搭配圖片來學習比較清楚。然後我本來想用DFS的方法，但是就會發生右子樹丟失的問題。這題真的很有趣，也很有挑戰性，希望自己在處理樹的方式更好。