如何将BST转换为矢量，为什么我的代码不工作?

Question

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;
}

它在编译时没有给出任何错误，但它也没有成功返回一些东西，可能是什么问题?

Answer 1

std::vector是一个容器，所以使用它。

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;
}

---

复制std::vector通常是非常昂贵的，您可以先学习一下序遍历。

Answer 2

问题是你试图访问一个未分配的指针的内存，首先发生在这里:v->push_back(root->data);.

1. 你需要创建一个矢量并将其地址保存在你的"v"指针如下:

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

如果您这样做，那么您需要通过释放部分结果向量来避免内存泄漏:

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

delete leftAns;  // see this line
}

模拟rightAns

2. 停止将变量命名为&;v&;， &; an&;，使用最好的命名方式!知道为什么了。

我的建议@zjyhjqs写:

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;
}