Pass vector by value accepted; pass vector by pointer/reference TLE??


  • 1
    R

    The following recursive code, in which a vector "trace" is passed by value is accepted by the OJ. But, I would imagine that passing the vector by value every call to aux wastes time because the vector gets copied, so I changed it to pass vector "trace" by reference or pointer. Both variations were rejected by OJ for TLE. That sounds very counterintuitive. Anyone has any ideas as to why?

    class Solution {
    public:
        vector<vector<int>> result;
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            //vector<vector<int>> result;
            vector<int> trace;
            if (root==NULL) return result;
            aux(root, sum, trace);
            return result;
        }
        
        void aux(TreeNode *root, int sum, vector<int> trace) {
            
            trace.push_back(root->val);
            if (root->left!=NULL) {
                aux(root->left, sum-root->val, trace);
            }
            if (root->right!=NULL) {
                aux(root->right, sum-root->val, trace);
            }
            if (root->left==NULL && root->right==NULL) {
                if (root->val == sum) {
                    result.push_back(trace);
                }
            }
        }
    };

  • 0
    T

    I have the same problem. hope someone give explanation


Log in to reply
 

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