Should Python be given more time?


  • 5
    R

    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;
            stack.add(root.val);
            if ((root.left == null) && (root.right == null)) {
                if (root.val == sum) {
                    ArrayList<Integer> ans = new ArrayList<Integer>();
                    for (Integer item: stack) ans.add(item);
                    res.add(ans);
                }
            } 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

  • 0
    L

    I also got TLE in python


  • 0
    Z

    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)
                    visited.add(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)
                    visited.add(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

  • 0
    G

    see my ac code.


  • 2
    G

    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

  • 0
    S

    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


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


  • 0
    K

    Now I see. Quite good!


  • 0
    D

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


  • 0
    Z

    Where is your code?


  • 0

  • 0
    V

    fantastic permission!!


Log in to reply
 

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