今日題目

題目連結：94. Binary Tree Inorder Traversal
題目主題：Stack, Tree, Depth-First Search, Binary Tree

前一篇Preorder Traversal分享完後，這次是Inorder Traversal觀念題。若沒看過前一篇，還是建議先往前看過Tree的觀念及Preorder Traversal會更好。

簡單說說 Inorder Traversal

在DFS（Depth-First Search）中Traversal分成三種方式：

1. Preorder
2. Inorder
3. Postorder

今天會用到的就是Inorder Traversal。
前一篇提到的Preorder原則是一進入節點就讀這個值，而Inorder不一樣的是第一次返回到節點才讀這個值。假設資料是 tree = [5, 2, 6, 1, 3, null, 8]

上圖中，每個節點上面的數字是讀的順序，而紅色虛線箭頭就是讀的方向。Inorder排出來就會是 [1, 2, 3, 5, 6, 8]，Inorder讀完的感覺是整棵樹越左邊的節點就會越先讀到，換一種方式看如下圖。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

今天的題目，目標就是用Inorder的方式來讀取樹，依照這個Inorder的順序將節點的值排到一個列表中，最後回傳這個列表。

約束：

• 樹的節點總數範圍在 [0, 100]
• 100 <= Node.val <= 100

範例1

輸入: root = [1,null,2,3]
輸出: [1,3,2]

範例2

輸入: root = []
輸出: []

範例3

輸入: root = [1]
輸出: [1]

範例4

輸入: root = [1,2]
輸出: [2,1]

範例5

輸入: root = [1,null,2]
輸出: [1,2]

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 寫一個遞迴方法，這個方法要能傳入前往的節點及要完成的list。
2. 每呼叫一次這個方法會往一個節點前進，
3. 這個遞迴會一直到走到發現沒有節點才會往回走。
4. 每當左邊子節點往回走，會把目前回到節點的值紀錄到list中。
5. 最終跑完所有節點會回傳一份用Inorder排出來的list。

圖解過程

範例：tree = [5, 2, 6, null, 8]

下圖中是實際上Traversal在走的過程，實際在想像移動過程的時候，建議在最下面的節點都補虛線的節點代表走到底了。

1. step1 從根節點進入以後，會直接走到左邊最底，回來以後的紅色圓，是要開始紀錄到list的第一個值。
2. step2 跟 step4 很像都是往右邊子節點前進，再往下層發現左邊子節點沒有值，回到紅色圈就是要紀錄的值。
3. step3 當右子節點走完以後會一路往上走，回到根節點，這時也是對根節點來說，是左邊的子節點走完了，因此要在這個時候紀錄這個根節點到list。
4. step5 會把剩下的虛線節點走完，確認整棵樹走過一次，再走回根節點結束這個Traversal。
5. 走完step1 ~ step5以後，就會組成step6看到的list，這個list是過程中出現的紅色圓一個一個組成的，也就是Inorder Traversal最後要回傳的結果。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:  
    # root 要進入的節點
    # inorder_list 最終要回傳的list  
    def traversal(self, root: TreeNode, inorder_list: List[int]):
        # 沒有節點往回走
        if root == None: return inorder_list
        # 前往左邊子節點
        inorder_list = self.traversal(root.left, inorder_list)
        # 左邊子節點回來以後，將目前節點的值紀錄到list中
        inorder_list.append(root.val)
        # 前往右邊子節點
        inorder_list = self.traversal(root.right, inorder_list)
        return inorder_list
    
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])
        

希望您今天能瞭解到...

1. Inorder Traversal
2. 94. Binary Tree Inorder Traversal的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：145. Binary Tree Postorder Traversal