Python recursive solution - O(n) 116ms

  • 0
    # 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:
            if sum == root.val and not root.left and not root.right:
            sum -= root.val
            self.findPath(root.left, sum, result, temp[:])
            self.findPath(root.right, sum, result, temp[:])

  • 0

    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

    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

    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:
        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.