LeetCode-Solutions/Python/path-sum.py at master · Monika-R/LeetCode-Solutions · GitHub

22 lines (17 loc) · 581 Bytes

# Time: O(n)

# Space: O(h), h is height of binary tree

class TreeNode(object):

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution(object):

# @param root, a tree node

# @param sum, an integer

# @return a boolean

def hasPathSum(self, root, sum):

if root is None:

return False

if root.left is None and root.right is None and root.val == sum:

return True

return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

Expand file tree