題目出處
144. Binary Tree Preorder Traversal
難度
easy
題目分類
Stack, Tree, Depth-First Search, Binary Tree
個人範例程式碼 – recursive 版
Tree 基本中的基本，我們一定至少需要學會兩種 parse tree 的方式，
- 一種是 iterative (直接的取)
- 另一種是 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# pre = m l r
if not root:
return []
else:
ans = [] # in-place change
self.dfs(root, ans)
return ans
def dfs(self, node, ans):
if not node:
return
else:
ans.append(node.val) # mid
self.dfs(node.left, ans) # l
self.dfs(node.right, ans) # r
return ans
算法說明
recursive 的 parse tree 基本上可以結合 dfs 的概念，
而我門需要另外寫一個 function dfs()，因為我們會需要把答案帶著走，原題目的函數沒辦法直接遞迴。
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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
# pre = m l r
ans = []
node_stack = [root]
while node_stack:
cur_node = node_stack.pop()
if cur_node:
ans.append(cur_node.val)
node_stack.append(cur_node.right)
node_stack.append(cur_node.left)
return ans
算法說明
直覺上的解法我們需要配合 Stack，遞迴的做法我們需要配合 DFS。
Stack 為 pop() 或 pop(-1) 就可以直接實現。
注意：由於「後處理要先放」，因此順序會是「先右後左」
你可能會想問這麼注意順序為什麼不用 Queue?
因為「先進先出」的結構我們沒辦法保存應該要後處理的東西。
例如 第一層的 左右，加入第二層後，
第一層的右一定會先出後，才會做第二層，因此沒辦法。
corner case 特殊情況處理
當樹為空 [] 或 為只有 root [1] 時，需要注意。
Boundary conditions/ Edge conditions 邊際情況處理
結束條件為 Stack 為空，我們運用 Stack 可以幫我們保存的概念。