題目：

給你一個二叉樹的根節點?root?，按?任意順序?，返回所有從根節點到葉子節點的路徑。

葉子節點?是指沒有子節點的節點。

示例 1：

輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]

示例 2：

輸入：root = [1]
輸出：["1"]

提示：

• 樹中節點的數目在范圍?[1, 100]?內
• -100 <= Node.val <= 100

思路：?

這道題目要求從根節點到葉子的路徑，所以需要前序遍歷（中左右），這樣才方便讓父節點指向孩子節點，找到對應的路徑。

先用遞歸的方法來做，走過的路徑用path來表示，每遍歷一個節點就加入到path中，遞歸遍歷節點

遞歸完，要做回溯，因為path 不能一直加入節點，它還要刪節點，然后才能加入新的節點。此時就需要用到回溯來刪走過的節點，回溯和遞歸是一一對應的，有一個遞歸，就要有一個回溯。

代碼及思路：

遞歸回溯：

# 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 = rightclass Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:# 定義一個列表來存儲路徑path = []# 定義一個列表來存儲結果result = []# 如果根節點為空，直接返回結果列表if not root:return result# 進行前序遍歷self.traversal(root, path, result)return resultdef traversal(self, node, path, result):# 將當前節點的值加入路徑中   path.append(node.val)# 如果當前節點是葉子節點，將路徑轉化為字符串并加入結果列表中  （中）if not node.left and not node.right:spath = '->'.join(map(str, path))result.append(spath)return# 如果有左子節點，進行遞歸遍歷，并將左子節點從路徑中彈出  （左）if node.left:self.traversal(node.left, path, result)path.pop()   # 回溯# 如果有右子節點，進行遞歸遍歷，并將右子節點從路徑中彈出  （右）if node.right:   self.traversal(node.right, path, result)path.pop()   # 回溯

迭代法：

# 定義二叉樹節點的類
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:# 使用棧來存儲節點stack = [(root)]# 使用棧來存儲路徑path_st = [str(root.val)]result = []while stack:# 彈出節點node = stack.pop()# 彈出路徑path = path_st.pop()# 如果節點沒有左右子節點，說明到達葉子節點，將路徑加入結果中if not node.left and not node.right:result.append(path)# 如果有右子節點，將右子節點和路徑加入棧中if node.right:stack.append(node.right)path_st.append(path + '->' + str(node.right.val))# 如果有左子節點，將左子節點和路徑加入棧中if node.left:stack.append(node.left)path_st.append(path + '->' + str(node.left.val))return result