Python3 解leetcode 範例112. Path Sum

題目出處：https://leetcode.com/problems/path-sum/

二叉樹 是不知道誰發明的資料型態 反正遇到了 解就對了

他二叉樹資料型態裡面有左子樹 跟 右子樹 也同樣都是 他自定義的二叉樹資料型態

其中裡面還有根值 總共三種屬性

則這次就是要找尋 加總剛好等於零的二叉樹路徑存不存在

如果存在return True 不存在就 return False

解法：

如果左右子樹都沒了 就代表到底了 因此就可以知道路走完了。

也就是說可以判端總合是否為零了。深度問題都推薦使用遞歸調用來解。

#Python3 代碼：

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        # 在這裡就用減法的方式如果到最底成減到最底層
        target =  targetSum - root.val

        # 在這裡下判斷如果 減到最底層的數值剛好是零 且 
	  # 確保已經到達最底層 所以再加個判斷式 左右子樹皆為空
        if target == 0 and not root.left and not root.right:
	     # 條件達成 路徑存在 把True 向上層傳遞
            return True
        
        if self.hasPathSum(root.left, target) or self.hasPathSum(root.right, target):
	     # 接收到來自下層的傳遞 因為是遞歸 所以繼續往上傳
            return True

以上。如有問題歡迎討論指教。有時間我在寫其他題目。