Leetcode 0112

Problem statement

https://leetcode.com/problems/path-sum/

Solution

Recursion, where we check for each sub-tree the values sum - node.value

Complexity

Time complexity is O(n), space is O(h).

Code

class Solution:
    def hasPathSum(self, root, sm):
        def dfs(node, v):
            if not node.left and not node.right: return v == node.val
            if node.left and dfs(node.left, v - node.val): return True
            if node.right and dfs(node.right, v - node.val): return True
            return False
        
        if not root: return False
        return dfs(root, sm)