# Python recursive solution - O(n) 116ms

• ``````# 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[:])``````

• 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

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

• 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)``````

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