Recursive algorithm using reference. Please help debug..


  • 0
    N

    The helper function uses the reference of the string, but for the test case
    [1,2,3,null,5] the answer is ["1->2->5","1->2-->3"]. But if I do not use reference, just pass the string itself as the parameter, it works well.

    can anyone help to figure out the bug?

        bool isleaf(TreeNode* node){
            return !node->left && !node->right;
        }
        void allPathHelper(TreeNode* root, vector<string>& result, string& temp  ){
            if(isleaf(root)){
                result.push_back(temp);
                return;
            }
            
            if(root->left){
                temp = temp + "->" + to_string(root->left->val);
                allPathHelper(root->left, result, temp);
                temp.pop_back();
            }
            
            if(root->right){
                temp = temp + "->" + to_string(root->right->val);
                allPathHelper(root->right, result, temp);
                temp.pop_back();
            }
        }
    
        vector<string> binaryTreePaths(TreeNode* root) {
            vector<string> result;
            if(!root)
                return result;
            string temp = to_string(root->val);
            allPathHelper(root, result, temp);
            
            return result;
        }
    '''

  • 0
    N

    Finally figured out, since the new value is possibly more than one character, and we also need to pop out "->".
    After changing to the following corresponding part, it works:
    '''
    if(root->left){
    int len = to_string(root->left->val).length();
    temp = temp + "->" + to_string(root->left->val);
    allPathHelper(root->left, result, temp);
    //the to_string(int) function may result in more than one character, so we cannot simply use the
    temp = temp.substr(0, temp.length() - len - 2);
    }
    '''


Log in to reply
 

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