今日題目

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

分享完 Preorder 及 Inorder 的Traversal以後，接下來是Postorder Traversal。建議還沒瞭解過Tree觀念的夥伴可以從本系列文 Day10 開始看，會對接下來的內容很有幫助。

簡單說說 Postorder Traversal

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

1. Preorder
2. Inorder
3. Postorder

今天會用到的就是Postorder Traversal。
Postorder的原則是，當目前節點的兩個子節點都確認過以後，才會讀取目前的節點。假設資料是 tree = [5, 2, 6, 1, 3, null, 8]

上圖中，每個節點上面的數字是讀的順序，而紅色虛線箭頭就是讀的方向。Postorder排出來就會是 [1, 3, 2, 8, 6, 5]，Postorder基本上就是從右邊子節點回來時，在讀目前回到節點上的值。

題目解說

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

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

約束：

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

範例1

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

範例2

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

範例3

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

範例4

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

範例5

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

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

解題的想像

文字描述

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

圖解過程

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

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

1. step1 跟 step3的步驟，可以觀察到紅色圓是要紀錄到list的節點，每個要紀錄的值一定會先把左、右的子節點都檢查過後，才會把這個節點的值記錄到list。
2. step2 及 step4 都是從右邊子節點直接回到上層節點，會往右邊子結點回到上層，代表左邊節點一定走完了，因此右邊子節點回上層以後，會紀錄上層這個節點的值。
3. step5 確認整棵樹走過一次以後，結束這個Traversal。
4. 走完step1 ~ step5以後，就會組成step6看到的list，這個list是過程中出現的紅色圓一個一個組成的，也就是Postorder Traversal最後要回傳的結果。

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

程式碼撰寫

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

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

1. Postorder Traversal
2. 145. Binary Tree Postorder Traversal 的解題方法

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

Next：100. same tree