LeetCode/solutions/108. Convert Sorted Array to Binary Search Tree.md

108. Convert Sorted Array to Binary Search Tree

思路

题意就是将有序数组转换为平衡搜索树。注意解是不唯一的，例如题中的例子如下解也是可以的:

      0
    /   \
 -10     5
   \      \
   -3      9

为了达到平衡，肯定要用二分的思想: 树根肯定是数组中间的那个数，左子树的根是数组左半边中间(mid=(left+right)/2)的数(计算mid的时候向上取整和向下取整均可， 题目例子向上取整就是leetcode给的结果，向下取整就是我这里给的结果)，右子树的根是数组右半边中间的数。由此可见是一个递归算法。
例如, [-10,-3,0,5,9]中间的数是0所以树根是0, 数组左半边[-10,-3]中间的数是-10，所以左子树的根是-10, 数组右半边[5,9]中间的数是5，所以右子树的根是5...如此递归下去即可。

C++

class Solution {
private:
    TreeNode* get_root(vector<int>& nums, int left, int right){
        if(left > right) return NULL;  // 递归出口
        int mid = left + (right - left) / 2; // 不写成mid=(left + right) / 2是为了防止溢出
        TreeNode* root = new TreeNode(nums[mid]);
        root -> left = get_root(nums, left, mid - 1);
        root -> right = get_root(nums, mid + 1, right);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return get_root(nums, 0, nums.size() - 1);
    }
};