Python recursive solution - O(n) 116ms


  • 0
    G
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param {TreeNode} root
        # @param {integer} sum
        # @return {integer[][]}
        def pathSum(self, root, sum):
            result = []
            self.findPath(root, sum, result, [])
    
            return result
    
        def findPath(self, root, sum, result, temp):
            if not root:
                return
    
            temp.append(root.val)
            if sum == root.val and not root.left and not root.right:
                result.append(temp)
                return
    
            sum -= root.val
            self.findPath(root.left, sum, result, temp[:])
            self.findPath(root.right, sum, result, temp[:])

  • 0
    S

    I think this solution is O(n^2) and not O(n). The problem is that

    self.findPath(root.left, sum, result, temp[:])

    The temp[:] is copying the entire array in each single recursive call


  • 0
    S

    I believe that in a correct implementation of DFS, you need to keep the temp as a stack and pop elements off the stack as you come out of a recursive call before you go into another call.


  • 0
    C

    Good answer, while you can also rewrite the code as:

    def pathSum(self, root, sum):
        if not root:
            return []
        res = []
        self.dfs(root, sum, [], res)
        return res
        
    def dfs(self, root, sum, ls, res):
        if not root.left and not root.right and sum == root.val:
            ls.append(root.val)
            res.append(ls)
        if root.left:
            self.dfs(root.left, sum-root.val, ls+[root.val], res)
        if root.right:
            self.dfs(root.right, sum-root.val, ls+[root.val], res)

Log in to reply
 

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