iT邦幫忙

0

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 = right
class 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%)

那我們下題見


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言