Python Solution with Detailed Explanation


  • 0
    G

    Solution
    Path Sum https://leetcode.com/problems/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
            else:
                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.