面试题 04.02：最小高度树

• 题目
• 解题
• • 方法一：先序遍历（递归）

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

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

          0 
         /  
       -3   9 
       /   / 
     -10  5 

为了二叉搜索树高度最小，就要使得左右子树，节点数，相差少，因此使用二分法，确定根节点。
先构造根节点，再构造左右节点。

class Solution {
public:
    TreeNode* helper(vector& nums,int left,int right){
        if(left>right) return nullptr;
        int mid=left+(right-left)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=helper(nums,left,mid-1);
        root->right=helper(nums,mid+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector& nums) {
        return helper(nums,0,nums.size()-1);
    }
};