題目出處
145. Binary Tree Postorder Traversal
難度
easy
題目分類
Stack, Tree, Depth-First Search, Binary Tree
解 Tree 樹問題的重點整理
這一篇的前身是以下連結，我們繼續在這篇整理重點
【Leetcode】python – [144] Binary Tree Preorder Traversal 個人解法筆記 (內含範例程式碼) 內含 處理 Tree 樹問題的重點
Tree 基本中的基本，我們一定至少需要學會兩種 parse tree 的方式，
- 一種是 iterative (直接的取)
- 另一種是 recursive (遞迴的取)
基本上這兩種都務必熟悉，未來解題時萬一一種解不出來，就可以嘗試用另外一種方法。
個人範例程式碼 - recursive 版
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
self.dfs(root, ans)
return ans
def dfs(self, root, ans):
if root:
self.dfs(root.left, ans)
self.dfs(root.right, ans)
ans.append(root.val)
算法說明
recursive 的 parse tree 基本上可以結合 dfs 的概念，
而我們需要另外寫一個 function dfs()，因為我們會需要把答案帶著走，原題目的函數沒辦法直接遞迴。
老實說個人覺得，Tree 系列的題目用 recursive 的概念是最接近原本學習知識觀念的解法XD。
寫起來非常直覺，而且稍微變化一下其他的解就都能直接跑出來。
主要變化的範圍如下，然後依照 (M)RL、R(M)L、RL(M) 改一下順序，全部的解法就都出來了!
- self.dfs(root.left, ans)
- self.dfs(root.right, ans)
- ans.append(root.val)
corner case 特殊情況處理
當樹為空 [] 或 為只有 root [1] 時，需要注意。
Boundary conditions/ Edge conditions 邊際情況處理
處理沒有節點的情況， if not root 直接回傳。
另外一種漂亮的解法：直接只處理 「if root:」，我們才做事情。
個人範例程式碼 - iterative 版
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [root]
# LR(M) -> (M)RL
while(stack):
if root: # left to leaf
ans.append(root.val) # add M first
stack.append(root.left) # record later
root = root.right
else: # can not left
root = stack.pop(-1)
return ans[::-1]
算法說明
我們要處理的問題變得比較麻煩一些，變成 LR(M),
但因為我們其實都是在控制 (M) 出現的時機，
因此比較好的方式是我們把它提造最前面去做，
因此我們以 (M)RL 去做一棵樹，而最後「再反序」。
我們分兩個 part
可以往下走的情況， (此處是往右先)
我們可以往右就右到底。
先加 (M)，存左，往右走
if root: # left to leaf
ans.append(root.val) # add M first
stack.append(root.left) # record later
root = root.right
不能往下走，就往左走的情況
表示上述 「if root」 找不到結果的情況，
pop 出「最後一個」「分歧點」，
也就是「回到上一個岔路往左走」。
else: # can not left
root = stack.pop(-1)
corner case 特殊情況處理
當樹為空 [] 或 為只有 root [1] 時，需要注意。
Boundary conditions/ Edge conditions 邊際情況處理
結束條件為 Stack 為空，我們運用 Stack 可以幫我們保存的概念。