C++自定义类型vector访问与BST转最小高度平衡树调试

自定义类型vector的元素访问方式 #

存储自定义类型（含自定义类型指针）的vector，元素访问逻辑和基础类型vector完全一致，没有特殊语法，常用访问方式有三种：

• 下标访问：vec[index] 直接返回对应位置元素，无边界检查；vec.at(index) 会做边界校验，越界时直接抛出out_of_range异常
• 迭代器访问：通过begin()/end()拿到迭代器后解引用即可获取元素，范围for是迭代器访问的语法糖
  你标注为Doubt Part的v1[mid]->left写法本身不存在语法错误，程序无输出是逻辑bug导致的崩溃，和vector访问方式无关

代码无输出的根因定位 #

你的程序运行后没有任何输出，核心原因是递归越界触发未定义行为+栈溢出，程序直接崩溃，具体bug点：

1. 递归终止边界传参错误
   solve函数中调用conversion时传入的结束索引是n，但vector的合法索引范围是0 ~ n-1，递归过程中会访问到v1[n]的野内存，同时触发无限递归打满调用栈，直接导致程序崩溃，后续所有打印逻辑都不会执行。

错误写法：TreeNode *l = conversion(v1, 0, n);
修正写法：TreeNode *l = conversion(v1, 0, n-1);

2. 未正确接收重构后的平衡树根节点
   conversion函数返回的是重构后平衡BST的根节点，你既没有在solve中把这个根节点向外传递，main函数计算平衡后树高时也仍然使用原来的斜树root，根本拿不到正确的平衡树高度。

3. 缺失头文件
   代码中使用max函数计算树高，但没有包含<algorithm>头文件，部分编译器下会直接编译报错。

修正后可运行代码 #

#include<iostream>
#include<vector>
#include<algorithm>
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)
{
    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;
   v1[mid]->left = conversion(v1, start, mid - 1);
   v1[mid]->right = conversion(v1, mid + 1, end);
   return v1[mid];
}

TreeNode* solve(TreeNode *root)
{
    vector<TreeNode*> v1;
    inorder_traversal(root, v1);
    int n = v1.size();
    cout << "节点总数：" << v1.size() << endl;
    TreeNode* new_root = conversion(v1, 0, n-1);
    cout << "中序序列：";
    for(auto itr : v1)
        cout << itr->val << " ";
    cout << endl;
    return new_root;
}

int height(TreeNode *root)
{
    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);
    TreeNode* balanced_root = solve(root);
    int height2 = height(balanced_root);
    cout << "转换前树高度：" << height1 << "\n";
    cout << "转换后平衡树高度：" << height2 << "\n";

    return 0;
}

运行结果 #

节点总数：5
中序序列：5 6 7 8 10 
转换前树高度：5
转换后平衡树高度：3

内容的提问来源于stack exchange，提问作者Kalash Jain