從LeetCode學演算法

0094. Binary Tree Inorder Traversal (Medium)

Question

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

1
2
3
4
5
6
Input: [1,null,2,3]
   1
    \
     2
    /
   3

1
Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

分析/解題

給定一個二元樹，題目要求以inorder(中序)方式回傳其節點值。
由於上一題的關係(讀者可以回頭參照第16篇)，我們已經講解過In-order的方式了，原則上就是經過左邊的部分->中間的部分->右邊的部分 的順序。
請留意這題輸出並不一定會由小到大(因為並沒有限制是二元搜尋樹)。

我們先來嘗試遞迴解法，通常較為簡單，這邊重新列出上一篇提到的：

1
2
3
4
5
6
inorder(root) {
  if root == NIL return
  inorder(root.left)
  print(root.val) // Or add/append to the list
  inorder(root.right)
}

若讀者感到不太能夠掌握這個流程的運作，可回頭參考第16篇的gif動畫。
總體而言，每次我們都會走到當前所能走到的左邊 ，直到左邊再也沒有node(變成NIL )時，會回到上一層 (return)，印出值 (或將其放到list中)，接著再往自身的右邊找 ；每次同樣的模式操作完以後，我們可以保證對於每個子樹，都是先拿到其左邊的節點值(們)，再來是自身，最後才是右邊的節點值(們)，從而保證這個演算法是得以遵照目標的順序完成的。

由於我們會使用一個ArrayList或List來存放inorder得到的值，所以下面是採用先宣告再將其放置到另一個遞迴用函式中處理的方式。當然，如讀者只想使用一個函式來遞迴，也可以宣告一個Solution的class變數，這樣就不需要每次傳遞了。兩者各有好處，讀者可依自己喜好決定。

Java

Python

那麼，如果是要求要迭代解(iterative solution)呢？
我們回顧一下前面的作法，遞迴的時候之所以我們能回到上一層，其實是因為我們的程式有記錄上一層的函式的執行狀態，從而在return時能返回到應該繼續的那一行執行。由於最後一層函式在返回時必須先被呼叫到 ，所以電腦在儲存時是採用Stack 的形式(因為要後進先出)。(這個堆疊又叫做The Stack或Call stack(呼叫堆疊))

因此，我們想要能夠不用遞迴解的話，
顯然我們應該要自己使用一個Stack來處理整個流程。

在In-order的流程中，首先我們是先一路走到最左邊的node，
中途經過的node我們應該要將其放進Stack中，這樣才能回到上一層去，
我們將這個node暫時命名為curr(current)。
curr一路向左最終一定會遇到NIL，表示這排從root一路向左邊走，
沿途的node全數放入到Stack中了。
那麼我們應該要將最後一個node從Stack中拿出來(因為後進先出，最後一個node應該是最左邊的node才對)，將其放到list當中。
接著將curr設為自己右邊的node。
反覆上面的流程，一直到curr和stack都空掉為止。

寫成虛擬碼如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
create a list named res
create a stack named stack
curr = root
while ( curr != NIL or !stack.isEmpty() ) {
    while (curr != NIL) {
        stack.push(curr)
        curr = curr.left
    }
    curr = stack.pop()
    res.add(curr.val)
    curr = curr.right
}
return res

Java

Python

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

「時間/空間複雜度？」
（O(N), O(N)，因為要走訪過整棵樹，且list要儲存整個二元樹攤平的結果）

「如果我將res放在class Solution的level有什麼優缺點？」
(優點：
有機會速度快一點點，且通常不用傳位址給函式，因為直接能存取到。
缺點：
對整個class均為可見，如果這個函式是要被反複使用的話，
要注意初始化的問題，且也有可能被其他函式修改到。)

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