# Should Python be given more time?

• I use the same algorithms, but accepted in Java and TLE in Python.

Since OJ is to practice the algorithms, they should be accepted or denied at the same time.
Right?

Here is my algorithms in both languages:

Java:

``````public class Solution {
public ArrayList<Integer> stack;
public ArrayList<ArrayList<Integer>> res;
public void search(TreeNode root, int sum) {
if (root == null) return;
if ((root.left == null) && (root.right == null)) {
if (root.val == sum) {
ArrayList<Integer> ans = new ArrayList<Integer>();
}
} else {
search(root.left, sum - root.val);
search(root.right, sum - root.val);
}
stack.remove(stack.size() - 1);
}
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
stack = new ArrayList<Integer>();
res = new ArrayList<ArrayList<Integer>>();
search(root, sum);
return res;
}
}
``````

And Python:

``````class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a list of lists of integers
def pathSum(self, root, sum):
stack = []
res = []
def search(root, sum):
if (root == None) or (root.val > sum): return
stack.append(root.val)
if (root.left == None) and (root.right == None):
if root.val == sum:
res.append(list(stack)) # copy stack to res
else:
search(root.left, sum - root.val)
search(root.right, sum - root.val)
stack.pop()
search(root, sum)
return res``````

• I also got TLE in python

• My accepted Python code. A little bit redundant (e.g., the usage of `visited`), but no TLE at least.

``````class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a list of lists of integers
def pathSum(self, root, sum):
if root is None:
return []
stack = []
result = []
visited = set()
curr = root
curr_sum = curr.val
stack.append(curr)
while len(stack) > 0:
while curr.left is not None and curr.left not in visited:
curr = curr.left
stack.append(curr)
curr_sum += curr.val
if curr.right is not None and curr.right not in visited:
curr = curr.right
curr_sum += curr.val
stack.append(curr)
else:
if curr.left is None and curr.right is None and curr_sum == sum:
result.append([node.val for node in stack])
curr = stack.pop()
curr_sum -= curr.val
curr = stack[-1] if len(stack) > 0 else None
return result``````

• see my ac code.

• my idea is:
after dealing a node, the sum will change,then record the path by adding the val to tag. when match the sum return the tag or empty list.

``````# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param root, a tree node
# @param sum, an integer
# @return a list of lists of integers
def pathSum2(self, root, sum,tag):
if root==None:
return []
if root.left==None and root.right==None and root.val==sum:
return [tag+[root.val]]
res=[]
if root.left!=None:
lres=self.pathSum2(root.left,sum-root.val,tag+[root.val])
res.extend(lres)
if root.right!=None:
rres=self.pathSum2(root.right,sum-root.val,tag+[root.val])
res.extend(rres)
return res
def pathSum(self, root, sum):
if root==None:
return []
if root.left==None and root.right==None and root.val==sum:
return [[root.val]]
res=[]
if root.left!=None:
lres=self.pathSum2(root.left,sum-root.val,[root.val])
res.extend(lres)
if root.right!=None:
rres=self.pathSum2(root.right,sum-root.val,[root.val])
res.extend(rres)
return res``````

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• ``````class Solution:
# @param root, a tree node
# @param S, an integer
# @return a list of lists of integers
def pathSum(self, root, S):
ret = []
stack = []
stack.append((root, []))
while not stack == []:
s = stack.pop()
n, vs = s
# empty tree wtf
if n is None:
continue
l = n.left
r = n.right
v = sum(vs)
# negative values
#if n.val + v > S:
#    continue
vs = vs + [n.val]
if l is None and r is None:
if n.val + v == S:
ret.append(vs)
if r is not None:
stack.append((r, vs))
if l is not None:
stack.append((l, vs))
return ret
``````

AC in 264ms

Note that in python function calls are expensive1. Use non-recursive ways instead.

• Now I see. Quite good!

• is there someone could tell me how to change my code not LTE

• fantastic permission!!

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