vector<int> *bstValuesToVector(BinaryTreeNode *root) {
    if (root == nullptr) {
        return nullptr;
    }

    vector<int> *v;

    vector<int> *leftAns = bstValuesToVector(root->left);
    vector<int> *rightAns = bstValuesToVector(root->right);

    if (leftAns != nullptr) {
        for (int i = 0; i < leftAns->size(); i  ) {
            v->push_back(leftAns->at(i));
        }
    }

    v->push_back(root->data);

    if (rightAns != nullptr) {
        for (int i = 0; i < rightAns->size(); i  ) {
            v->push_back(rightAns->at(i));
        }
    }

    return v;
}

It is not giving any error on compiling, but it is also not successfully returning something, what can be the problem ?

CodePudding user response：

std::vector is a container, so just use it.

struct BinaryTreeNode {
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    int data;
};

std::vector<int> bstValuesToVector(BinaryTreeNode *root) {
    if (root == nullptr) {
        return {};
    }

    std::vector<int> v;

    std::vector<int> leftAns = bstValuesToVector(root->left);
    std::vector<int> rightAns = bstValuesToVector(root->right);

    // for (int i = 0; i < leftAns.size(); i  ) {
    //     v.push_back(leftAns[i]);
    // }
    for (auto data : leftAns) {
        v.push_back(data);
    }

    v.push_back(root->data);

    // for (int i = 0; i < rightAns.size(); i  ) {
    //     v.push_back(rightAns[i]);
    // }
    for (auto data : rightAns) {
        v.push_back(data);
    }

    return v;
}

Copying a std::vector is usually very expensive, you could take a lesson of Inorder Traversal at first.

CodePudding user response：

The problem is you are trying to access the memory of a not allocated pointer that first occurs here : v->push_back(root->data);.

1. You need to actually create a vector and keep its address into your "v" pointer as follows :

   vector<int> *v = new vector<int>();

If you do this, then you need to avoid the memory leak by releasing your partial result vectors :

if (leftAns != nullptr) {
    for (int i = 0; i < leftAns->size(); i  ) {
        v->push_back(leftAns->at(i));
    }


    delete leftAns;  // see this line
}

Analog for rightAns

2. Stop naming your variables as "v", "Ans", use the best naming you can! See why.

My suggestion as @zjyhjqs written:

struct BinaryTreeNode {
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    int data;
};

std::vector<int> bstValuesToVector(BinaryTreeNode *root) {
    if (root == nullptr) {
        return {};
    }

    std::vector<int> result;

    std::vector<int> leftData = bstValuesToVector(root->left);
    std::vector<int> rightData = bstValuesToVector(root->right);

    for (auto data : leftData) {
        result.push_back(data);
    }

    result.push_back(root->data);

    for (auto data : rightData) {
        result.push_back(data);
    }

    return result;
}