Skip to main content

112 - Path Sum

Details​

KeyValue
Linkhttps://leetcode.com/problems/path-sum/
LanguagePython 3
Runtime40 ms, faster than 97.79% of Python3 online submissions for Path Sum
Memory Usage15.1 MB, less than 56.50% of Python3 online submissions for Path Sum
DatastructuresTreeNode
AlgorithmsDFS
ComplexityTime: O(N) Memory: O(N)

Procedure​

  1. ...

Code​

# 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
        if not root.left and not root.right and root.val == targetSum: return True
        return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)