LeetCode 0108. Convert an ordered array into a binary search tree - the median of the array is the root, and the left and right of the median are the left and right subtrees respectively

【LetMeFly】108. Convert an ordered array to a binary search tree - The value in the array is the root , The left and right median values are respectively left and right subtrees

Force button topic link ：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

Give you an array of integers nums , Where elements have been Ascending array , Please turn it into a Highly balanced Binary search tree .

Highly balanced A binary tree is a tree that satisfies 「 The absolute value of the height difference between the left and right subtrees of each node does not exceed 1 」 Two fork tree .

 

Example 1：

 Input ：nums = [-10,-3,0,5,9]
 Output ：[0,-3,9,-10,null,5]
 explain ：[0,-10,5,null,-3,null,9]  Will also be considered the right answer ：

Example 2：

 Input ：nums = [1,3]
 Output ：[3,1]
 explain ：[1,null,3]  and  [3,1]  They're all highly balanced binary search trees .

 

Tips ：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums Press Strictly increasing Sequential arrangement

In fact, I think it's good to set the difficulty of this question to medium

Method 1 ： The value in the array is the root , The left and right median values are respectively left and right subtrees

seeing the name of a thing one thinks of its function , To make this tree a highly balanced binary search tree , We just need to take the median of the array as the root .

Because take the median of the array as the root , The number of elements on the left and right is equal ( Or one difference ) The effect of .

meanwhile , What the title gives is an array that has been sorted , Therefore, the elements on the left of the value in the array are all smaller than the median elements , All on the right are larger than .

Therefore, the left side of the median is regarded as the left subtree , All the right trees can be regarded as right subtrees .

This becomes a sub problem ： Construction of left and right subtrees . So recursion is enough .

Termination conditions ： The array to be built is empty .

• Time complexity $O(n)$, among $n$ Is the number of elements in the array .
• Spatial complexity $O(\log n)$, Depending on the depth of the recursive stack .

AC Code

C++

class Solution {
    
private:
    TreeNode* build(vector<int>& nums, int l, int r) {
    
        if (l >= r)
            return nullptr;

        int mid = (l + r) >> 1;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = build(nums, l, mid);
        root->right = build(nums, mid + 1, r);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
    
        return build(nums, 0, nums.size());
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125610878