leetcode with python:112. Path Sum

题目:

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

给定一个binary tree和一个目标值(target),看是否有一条root->leaf路径上的值总和等于target

连续第n题树(累...),以下是我的想法

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:        def getsum(root,val,tar=targetSum):            if not root:                return False                            val=val+root.val                        if root.left==None and root.right==None:                return val==tar            else:                return getsum(root.left,val) or getsum(root.right,val)                        return getsum(root,0)

由root不断递迴往下加,直到发现到达了leaf,回传这条加总值是否等于target
这里有个重点,递迴回传两侧布林值时要用or
因为只要有一侧的sum等于target,整个function就该回传True(存在一条root->leaf路径上的值总和等于target)
而且这样遇到一侧是None直接回传False也没差(因为是用or)
最后执行时间38ms(faster than 98.48%)

那我们下题见