Why my python code is OLE/TLE but the nearly same C++ code is AC with 56ms?


  • 0
    Q

    I'm new in Python, and I don't know what's wrong in my python code. I think it's completely the same with my C++ code (DFS).

    Python OLE code:

    class Solution:
        # @param root, a tree node
        # @param sum, an integer
        # @return a list of lists of integers
        def pathSum(self, root, sum):
            pathAll = [];
            if not root:
                return pathAll;
            path = [];
            
            def dfs(node, sum, path):
                if not node.left and not node.right:
                    if sum == node.val:
                        path1 = path;
                        path1.append(sum);
                        pathAll.append(path1);
                    return
                path.append(node.val);
                if node.left:
                    dfs(node.left, sum-node.val, path);
                if node.right:
                    dfs(node.right, sum-node.val, path);
                path.pop();
                
            dfs(root, sum, path);
            return pathAll;
    

    Python TLE code:

    class Solution:
        # @param root, a tree node
        # @param sum, an integer
        # @return a list of lists of integers
        def pathSum(self, root, sum):
            pathAll = [];
            if not root:
                return pathAll;
            path = [];
            
            def dfs(node, sum, path):
                if not node.left and not node.right:
                    if sum == node.val:
                        path1 = path;
                        path1.append(sum);
                        pathAll.append(path1);
                    return
                path2 = path;
                path2.append(node.val);
                if node.left:
                    dfs(node.left, sum-node.val, path2);
                if node.right:
                    dfs(node.right, sum-node.val, path2);
                
            dfs(root, sum, path);
            return pathAll;
    

    C++ AC code:

    class Solution {
    public:
        void dfs(TreeNode *node, int sum, vector<int> &path, vector<vector<int> > &ret)
        {
            if (!node->left && !node->right)
            {
                if (node->val == sum)
                {
                    path.push_back(sum);
                    ret.push_back(path);
                    path.pop_back();
                }
                return;
            }
            path.push_back(node->val);
            if (node->left)
                dfs(node->left, sum-node->val, path, ret);
            if (node->right)
                dfs(node->right, sum-node->val, path, ret);
            path.pop_back();
        }
        
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            vector<vector<int> > ret;
            if (!root)
                return ret;
            vector<int> path;
            dfs(root, sum, path, ret);
            return ret;
        }
    };

  • 0
    D

    Maybe you used recursively call. It will paly more time. At firset I used recursively call I got OLE too. Below is my code which is not implemented by recursively.

     def pathSum(self, root, sum):
        result = []
        stack = []
        if root == None:
            return result
       
        
        stack.append((root, []))
    
        while stack != []:
            node, l = stack.pop()
            l.append(node.val)
    
            if node.left == None and node.right == None:
                lSum = 0  
                for x in l:
                    lSum += x
                if lSum == sum:
                    result.append(l)
            else:
                if node.left != None:
                    stack.append((node.left, l[:]))
                if node.right != None:
                    stack.append((node.right, l[:]))
        return result

  • 0
    H

    Your code segments exemplify a fundamental difference between C/C++ and Python: the two languages treat 'variables' in two different ways. In C/C++, a variable is associated with a certain storage space in memory which is specified when it is defined. When you assign a new value to a variable, the content of its piece of memory is rewritten. In Python, everything is an object, and a variable can be seen as a name bound to a certain underlying object. The binding is not permanent. Whenever assignment happens, you are binding/rebinding a name to an object. For example, you meant to use the directive

             path1 = path 
    

    in your Python code to creat a new list object path1 to hold a copy of the content of path. This should work in C++ with STL vector. However, Python reads the line as: create a new name path1, and bind it to the same object that path is bound to. Therefore, all the way through your code you are appending to the same list object, and appending references to that same list object to your results list.

    I had the same confusion when I started to write Python and I think it is a very common mistake to make. I'd suggest some reading on a related topic about how does Python pass arguments, which I found extremely helpful for clarifying such confusion.


  • 0
    P

    I can solve your question. Actually, if you write recursion dfs out of pathSum, you will pass the test cases. this is my code, 100ms:

    class Solution:
        # @param root, a tree node
        # @param sum, an integer
        # @return a list of lists of integers
        
        def search(self, root, p):
            if not root:
                return
            if not root.left and not root.right:
                if root.val == p:
                    self.ans.append(self.num[:]+[root.val])
                return
            self.num.append(root.val)
            self.search(root.left, p-root.val)
            self.search(root.right, p-root.val)
            self.num.pop()
        
        def pathSum(self, root, sum):
            self.ans = []
            self.num = []
            self.search(root, sum)
            return self.ans

Log in to reply
 

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