问一下一个数据结构的简单题目，另外有关(vector<int> &num,多谢！

问一下一个数据结构的简单题目，另外有关(vector<int> &num,谢谢！！！！！！！！！！！！！！！！！！。。。。。。。。。。。。。。。。。。。。。。
题目：给一个升序数组，求一棵高度平衡的二分检索树，高度平衡是指左右子树的高度最大相差1，二分检索树是，根节点的左子树的所有节点值都小于等于根节点，右子树的所有节点值都大于等于根节点，左右子树也是二分搜索树。

/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution

{

public:

    void build(vector<int> &num, TreeNode * &root, int left, int right)

    {

        if(left>right)

            return;

        int mid = (left+right)/2;

        root = new TreeNode(num[mid]);

        build(num, root->left, left, mid-1);//我的理解递归时，这一行的left永远为0，下一行的right永远为 len-1，但替换后会报错，不知道为什么？

        build(num, root->right, mid+1, right);//

    }

    TreeNode *sortedArrayToBST(vector<int> &num)

    {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        int len = num.size();

        TreeNode * root = NULL;

        if(len>0)

            build(num, root, 0, len-1);

        return root;

    }

};

注释处有个问题；另外vector<int> &num到底是什么意思理解的不明确，为什么每次递归都要 build(num，。。。。）
谢谢
------解决方案--------------------
我感觉楼主对递归的理解还不是很透彻，建议有空的时候自己写个最简单的递归好好体会一下，比如阶乘或者斐波那契。最好是用调试器单步运行看看每次调用参数的变化，同时在纸上画几个图加深理解。

举例：第一次调用build, left=0, right=15，接下来
left=0, right=7
    进来之后继续
    left=0, right=3
    left=4, right=7  // 这里的right不是len-1
left=8, right=15
    left=8, right=11  // 这里的left不是0
    left=12, right=15

------解决方案--------------------

引用:

看到有人写vector<int> num 和 vector<int> &num的区别在哪？谢谢

这两个实际上是同一个东西，有&的是引用。
建议楼主打开教材，找到讲引用的那一节学习一下，或者看看《高质量c++/c编程指南》里面讲的引用，然后再google一下“按值传递按引用传递”
------解决方案--------------------
vector的引用啊，不发生拷贝，楼主可以自己写个类型，写上类型的拷贝构造函数来测试下
比方定义个类 CMyCls
fun1( vector<CMyCls> vec);

fun2( vector<CMyCls>& vec);

函数调用的时候，看看CMyCls的拷贝构造函数，可以在里面打印点东西

问一下一个数据结构的简单题目，另外有关(vector &num,多谢！

相关推荐