Python Solution with Detailed Explanation

  • 0

    Path Sum

    • If we have a null tree and target = 0, the rule here is to return False.
    • If current node is None, return False.
    • If we are at leaf node and target == root.val, then return True.
    • If we are non null and non leaf node, explore left and right subtree for sum-root.val.
    • Time and Space Complexity: O(N)
    class Solution(object):
        def hasPathSum(self, root, sum):
            :type root: TreeNode
            :type sum: int
            :rtype: bool
            if root is None:
                return False
            elif root.left is None and root.right is None:
                return root.val == sum
                return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.