递归生成指定范围节点数据vector时出现push_back匹配错误

编译错误信息 #

no instance of overloaded function "std::vector<_Tp, _Alloc>::push_back [with _Tp=int, _Alloc=std::allocator<int>]" matches the argument listC/C++(304)
ex1.cpp(116, 12): argument types are: (std::vector<int, std::allocator<int>>)
ex1.cpp(116, 12): object type is: std::vector<int, std::allocator<int>>

问题代码 #

vector<int> rangeBWVec(binaryTreeNode<int>* root,int min, int max){
    
    vector<int> re;
    if(root==NULL){

        return re;
    }
    if(root->data>=min)
    {
        re.push_back(rangeBWVec(root->left,min,max));
    }

    if(root->data>=min && root->data<=max)
        re.push_back(root->data);

    if(root->data<=max)
    {
       re.push_back(rangeBWVec(root->right,min,max));
    }
    
}

错误原因 #

核心问题是递归调用rangeBWVec返回的是vector<int>类型，但vector<int>::push_back仅接受单个int参数，直接将整个vector传入会导致类型不匹配。另外原代码末尾漏掉了return re;语句，违反了函数的返回值约定。

解决方案 #

方案1：使用insert合并递归结果 #

通过vector::insert方法将递归返回的vector中的元素逐个插入到当前vector的末尾，替代错误的push_back：

vector<int> rangeBWVec(binaryTreeNode<int>* root,int min, int max){
    
    vector<int> re;
    if(root==NULL){
        return re;
    }
    if(root->data>=min)
    {
        vector<int> leftRes = rangeBWVec(root->left, min, max);
        re.insert(re.end(), leftRes.begin(), leftRes.end());
    }

    if(root->data>=min && root->data<=max)
        re.push_back(root->data);

    if(root->data<=max)
    {
        vector<int> rightRes = rangeBWVec(root->right, min, max);
        re.insert(re.end(), rightRes.begin(), rightRes.end());
    }
    
    return re;
}

方案2：引用传递结果（更高效） #

使用辅助函数，通过引用参数传递结果vector，避免递归过程中频繁创建和拷贝vector，提升效率：

// 递归辅助函数
void rangeBWHelper(binaryTreeNode<int>* root, int min, int max, vector<int>& result) {
    if(root == NULL) return;
    
    if(root->data >= min) {
        rangeBWHelper(root->left, min, max, result);
    }
    
    if(root->data >= min && root->data <= max) {
        result.push_back(root->data);
    }
    
    if(root->data <= max) {
        rangeBWHelper(root->right, min, max, result);
    }
}

// 对外暴露的接口函数
vector<int> rangeBWVec(binaryTreeNode<int>* root, int min, int max) {
    vector<int> result;
    rangeBWHelper(root, min, max, result);
    return result;
}

内容的提问来源于stack exchange，提问作者Souman Kajaria