使用DFS 模板 + 基礎圖論題目 Binary Tree Paths Leetcode #257

這題題目在這裡:

題目會給定一顆樹，要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。

測試範例:

Example 1:

Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1]
Output: ["1"]

約束條件:

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• -100 <= Node.val <= 100

演算法:

如同在這篇演算法DFS/BFS筆記所提到的， 展開整個搜索空間(Search space/State space)的題目，常常結合回溯法backtracking一起使用，那最適合的就是DFS深度優先演算法了。

再次複習、回憶 深度優先+回溯法的模板 DFS template + backtracking:

def dfs(parameter):
　
　# 終止條件 Stop condition
　if stop condition:

　　# update final result if needed
　　return result
　

　# 通則 General cases
　for each possilbe next selection:

　　make a selection
　　dfs(updated parameter)
　　undo selection

　return result

比較簡潔地講，所有從根節點到葉子節點的路徑，都可以抽象表達為

Root -> 左子樹路徑 , 或者

Root -> 右子樹路徑 這兩種形式。

程式碼:

class Solution:
　 def binaryTreePaths(self, root: TreeNode) -> List[str]:

　　  path = []
　　  
　　  ## base case: empty tree
　　  if not root:
　　　　return path
　　  
　　  ## base case: leaf node
　　  if not root.left and not root.right:
　　　　path.append( f"{root.val}" )
　　　　return path
　　  
　　  ## General cases:
　　  
　　  for leftPath in self.binaryTreePaths(root.left):
　　　　path.append( f"{root.val}->{leftPath}")
　　　　
　　  for rightPath in self.binaryTreePaths(root.right):
　　　　path.append( f"{root.val}->{rightPath}")
　　　　
　　  return path

時間複雜度:

O( n² )

總共O(n)個節點，每個節點至多拜訪一次，每個節點需要拷貝和更新當下的路徑，耗費O(n)

空間複雜度:

O( n² )

總共O(n)個節點，遞迴深度最深為O(n)，每一層遞迴需要拷貝和更新當下的路徑，耗費O(n)

Reference:

[1] Python/JS/Java/C++ by self-recursion [+ Comment] — Binary Tree Paths — LeetCode