112.路徑總和

• 2020 年 6 月 15 日
• 筆記
• 力扣中國-每日一題

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# 這道題就是用深搜算法來做的，只要找出一個和為sum的就可以
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        # 定義一個變量，用來存放每次求出的和
        num_sum = 0
        return self.dfs(root,num_sum,sum)
    # 深搜函數
    def dfs(self,root,num_sum,sum):
        # 這條語句是用來判斷根節點是否為空的。
        if not root: return False
        num_sum += root.val
        # 注意這裡，不能遍歷到葉子節點，因為那樣就會返回False。
        if not root.left and not root.right and num_sum == sum :
            return True
        # 注意這裡一定是or，
        return self.dfs(root.left,num_sum,sum) or self.dfs(root.right,num_sum,sum)