如何访问用户自定义数据类型的vector对象的元素?他们有什么特殊的方法，因为传统的方法不起作用 &

Question

我被数据结构和算法的一个问题卡住了。问题是如何从给定的二叉搜索树(BST)构造最小高度的二叉搜索树(BST)。为了更清楚，这里是问题的链接

将正常BST转换为平衡BST

这是我的解决方案:

#include<iostream>
#include<vector>
using namespace std;
struct TreeNode{
int val;
TreeNode *left, *right;
TreeNode(int data)
{
this->val = data;
this->right = NULL;
this->left = NULL;
}
};
void inorder_traversal(TreeNode *root, vector<TreeNode*> &v1)// Inorder traversal of tree
{
if(!root)
return;
inorder_traversal(root->left, v1);
v1.push_back(root);
inorder_traversal(root->right, v1);
}
TreeNode* conversion(vector<TreeNode*> &v1, int start, int end) //
{
if(start > end)
return NULL;
int mid = (start + end) / 2;
//-----------Doubt Part----------//
v1[mid]->left = conversion(v1, start, mid - 1);// I think this part is not working well
v1[mid]->right = conversion(v1, mid + 1, end);
return v1[mid];
//-------------------------------//
}
void solve(TreeNode *root) // main function 
{
vector<TreeNode*> v1;
inorder_traversal(root, v1);// function to get the inorder traversal of the given tree
int n = v1.size();
cout << v1.size();
TreeNode *l = conversion(v1, 0, n);// function to convert given tree to min height BST
for(auto itr : v1)
cout << itr->val << " ";
}
int height(TreeNode *root) // function to calculate the height of the BST tree
{
if(!root)
return 0;
int hl = height(root->left);
int hr = height(root->right);
return 1 + max(hl, hr);
}
int main()
{
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(8);
root->left->left = new TreeNode(7);
root->left->left->left = new TreeNode(6);
root->left->left->left->left = new TreeNode(5);
int height1 = height(root);
solve(root);
int height2 = height(root);
cout << "Initial height before the conversion :" << height1 << "n";
cout << "Final height after the conversion :" << height2 << "n";
return 0;
}

基本上，在执行当前代码后，我没有得到任何输出，我认为问题是因为Doubt部分而发生的。

谁能帮我一下这个代码?

Answer 1

一个问题是您不知道end在您的代码中意味着什么。你需要做出决定。它是范围的最后一个元素的索引，还是再往前一个元素的索引?

如果它是范围的最后一个元素的索引，那么conversion(v1, 0, n)是错误的(应该是conversion(v1, 0, n-1))。

如果它是一个过去，那么if (start > end)是错误的(应该是if (start >= end))，conversion(v1, start, mid - 1)也是错误的(左作为练习)。

注意:在c++中，end按惯例表示"超出范围"。如果你想要"最后一个索引"也就是说，将索引命名为first和last。

另一个问题是，转换前的根不再是转换后的根。solve暂时拥有新的根，但随后将其丢弃并且不返回任何内容，因此main拥有错误的根。