LeetCode 108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

题目大意：给一个升序数组，把它转化为一个高度平衡的二叉搜索树～

分析：设立left和right，mid = (left + right) / 2，每次将数组的中点mid的值为根结点的值，中点左边为根结点的左子树，右边为根结点的右子树～递归求解～

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

class Solution {

public:

TreeNode* sortedArrayToBST(vector<int>& nums) {

return func(nums, 0, nums.size() - 1);

}

private:

TreeNode* func(vector<int>& nums, int left, int right) {

if (left > right) return NULL;

int mid = (left + right) / 2;

TreeNode* root = new TreeNode(nums[mid]);

root->left = func(nums, left, mid - 1);

root->right = func(nums, mid + 1, right);

return root;

}

};

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版