编程题-最小高度树

题目：

给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。

解法一（二分查找+二叉搜索树构建）：

二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排列的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。二叉搜索树中，左子树的值要小于根节点的值要小于右子树的值，因此选择二分查找的方式选取升序数组序列中的元素，选择中间位置右边的数组作为根节点，根节点的下标为mid=(left+right+1)/2，此处的除法为整数除法。如下为笔者代码：

class Solution {
public:
    //采用TreeNode*& root来索引二叉树，将二分查找的中间元素作为跟节点添加到二叉搜索树中
    //将中间元素的左子数组序列作为左子树创建新的二叉搜索树，将中间元素的右子数组序列作为右子树创建新的二叉搜索树。
    //TreeNodeInsert递归函数的执行条件是left<=right，仅填了left=right时的最后一个元素作为根节点元素，不再执行递归函数体中的递归内容
    void TreeNodeInsert(TreeNode*& root, vector<int>& nums, int left, int right){
        int T = (left+right+1)/2;
        if(root==nullptr){
            root = new TreeNode(nums[T]);
        }
        if(left<=T-1 and root->left==nullptr){
            TreeNodeInsert(root->left, nums,left, T-1);
        }
        if(T+1<=right and root->right==nullptr){
            TreeNodeInsert(root->right, nums,T+1,right);
        }
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int length = nums.size();
        int T = length/2;
        int left = 0;
        int right = length-1;
        if(length==0){
            return nullptr;
        }
        创建的left和right两个指针为子升序数组的首部和尾部索引值
        TreeNode* root = nullptr;
        TreeNodeInsert(root, nums,left,right);
        return root;
    }
};

时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。

空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(logn)。

笔者小记：

1、创建一个新的空二叉树，TreeNode* root = nullptr；必须加*指针，否则会产生错误。

2、创建二叉树的索引TreeNode*& root，后续对root的修改则会直接修改原来的二叉树，必须加&引用符号，否则后续对root的修改只会改变函数体内的root二叉树，不能对函数体外root二叉树内容进行修改。

TreeNode*& root是一个引用类型的指针参数，它表示传递的是指向TreeNode*的引用，当传递给函数时，函数内部可以直接修改原始root指针的值，甚至可以改变它指向的地址，对指针指向的内存地址和变量的任何修改都将反映在原始的指针上。

TreeNode* root是一个普通的指针类型参数，表示传递的是TreeNode*类型的值（即一个指针副本）。在函数内部，可以修改指针所指向的内容，但是修改指针本身（例如指向其他内存地址）并不会影响原始的root指针。简单来说，函数内对指针的修改仅限于局部作用域，外部的root不会受到影响。

3、如果要在小记1、中root空二叉树的基础上增加根节点代码为root = new TreeNode(value)；采用new创建二叉树节点，此时TreeNode* root ！=nullptr，将不再为空。

之前题目涉及到的都是二叉树和二叉搜索树的遍历，本次题目与之前二叉树相关的都不相同，涉及到的是二叉树的创建和新增根节点操作代码，需特别关注和记录。