710 - Python LeetCode

【Leetcode】python - [257] Binary Tree Paths 個人解法筆記

題目出處

257. Binary Tree Paths

難度

easy

個人範例程式碼

# 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]:
        ans = []
        self.dfs(root, "", ans)
        return ans

    def dfs(self, root, path, ans):
        if not root: # Null point
            return

        if not root.left and not root.right: # last point
            path += f"{root.val}"
            ans.append(path)
            return

        path += f"{root.val}->"
        self.dfs(root.left, path, ans)            
        self.dfs(root.right, path, ans)

        return

算法說明

基礎的 DFS 用來 traverse Tree 裡面的內容，並回傳路徑。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

如果沒有內容，回傳 []

Boundary conditions

end of recursion

判斷 Null 或是 Leaf

  • Null
if not root: # Null point
  • Leaf
if not root.left and not root.right: # last point

define of recursion

單純增加路過的路徑。

path += f"{root.val}->"

split of recursion

拆成兩路

self.dfs(root.left, path, ans)            
self.dfs(root.right, path, ans)

Reference