題目敘述: Binary Tree Paths
要求我們輸出所有從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
