Why my solution TLE?


  • 0
    S

    Hello everyone! I wrote the following algorithm to check every root-to-leaf path and add valid ones to the answer vector. I think this is the best time complexity we could achieve, but why is my solution TLE?
    Here's my code:

    class Solution {
    public:
        // vector to record answers
        vector<vector<int>> ans;
        // vector to record current path
        vector<int> st;
        
        // this function goes from root to leaf to check every path
        // node: which node we are processing
        // des: the total value of tree path so far
        void calc(TreeNode* node, int des)
        {
            // add this node's value to current path
            st.push_back(node->val);
            // calculate new value including this node
            int total = des + node->val;
            // if this is a leaf node
            if (!node->left && !node->right)
            {
                // check whether this path is valid, if it is, add it to the answer vector
                if (total == des)
                    ans.push_back(st);
                return;
            }
            // otherwise this node is not a leaf node
            // if left child exists, recursively check it
            if (node->left)
                calc(node->left, total);
            // if right child exists, recursively check it
            if (node->right)
                calc(node->right, total);
            // all children have been checked, so we remove this node'value from current path
            st.pop_back();
        }
        
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            // clear answer vector
            ans.clear();
            // if NULL is passed, just return empty vector
            if (!root)
                return ans;
            // clear path vector
            st.clear();
            // check from root with initial sum 0
            calc(root, 0);
            // return all answers
            return ans;
        }
    };

  • 0
    S

    Could you please update your question to explain your algorithm and make some comment in your code?


  • 0
    S

    i'm sorry. Here's my updated question.


  • 1
    S
            if (!node->left && !node->right)
            {
                // check whether this path is valid, if it is, add it to the answer vector
                if (total == des)
                    ans.push_back(st);
                // ERROR HERE
                return;
            }
    

    See the comment ERROR HERE line, when it is a leaf, this level of recursion will return from here, but your st do not pop, these may lead to large size of st, and I guess it take long time to push_back to ans, so it leads to TLE.


  • 0
    S

    Thanks a lot! It's just the problem. :-)


  • 0
    S

    And I just find another problem that I should compare "total" to "sum" but not to "des".


  • 0
    G

    An alternative to avoid pop_backs : Pass 'st' as an argument like

    calc(TreeNode* node, int des, vector<int> v)


  • 0
    L

    pop may be more important reason


Log in to reply
 

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