1. 題目
給定一個有序整數數組，元素各不相同且按升序排列，編寫一個算法，建立一棵高度最小的二叉搜尋樹。
示例:
給定有序數組: [-10,-3,0,5,9],
一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜尋樹：
0
/ \
-3 9
/ /
-10 5 複制
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/minimum-height-tree-lcci
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
- 二叉搜尋樹中序周遊是有序的
- 每次找到數組的中點作為root
- 遞歸處理
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums,0,nums.size()-1);
}
TreeNode* build(vector<int>& nums, int l, int r)
{
if(l > r)
return NULL;
int mid = l+((r-l)>>1);
TreeNode* root = new TreeNode(nums[mid]);
root->left = build(nums,l,mid-1);
root->right = build(nums,mid+1,r);
return root;
}
}; 複制
