題目:

Given the root of a binary tree, return all root-to-leaf paths in any order.

給定一棵binary tree,回傳所有root-to-leaf路徑

老樣子用遞迴來實作的樹題

# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
        record=[]
        path=""
        def ans(root,record,path):
            if path=="":
                path=path+str(root.val)
            else:
                path=path+"->"+str(root.val)
            
            if root.right:
                ans(root.right,record,path)
            if root.left:
                ans(root.left,record,path)
            if not root.right and not root.left:
                record.append(path)
                
            return record
        
        return ans(root,record,path)

從root開始設一個空字串(path)放入路過的點
開始往左往右走
隨著遞迴的深入path也會越來越多
當到達leaf時就停止紀錄,此時path紀錄的就是其中一個root-to-leaf路徑
所以將path放入record再回傳record
回傳到最後record就紀錄了所有root-to-leaf路徑
最後執行時間29ms(faster than 97.51%)

那我們下題見