Leetcode Study Day 50

Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a
height-balanced binary search tree.

Example 1:


Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Example 2:


Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
 

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in a strictly increasing order.

Solution

We use a recursion method to create the tree. Firstly, we find the median of the array and create a node with the median. Then we call the function recursively to create the left and right subtree. The left subtree is created by the left half of the array and the right subtree is created by the right half of the array.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return nullptr;
        int medianInd = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[medianInd]);
        vector<int> left(nums.begin(),nums.begin()+medianInd);
        vector<int> right(nums.begin()+medianInd+1,nums.end());
        root -> left = sortedArrayToBST(left);
        root -> right = sortedArrayToBST(right);
        return root;
    }
};