108. Convert Sorted Array to Binary Search Tree

Posted on Edited on In

108. Convert Sorted Array to Binary Search Tree

Description

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

Example 1:

1
2
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:

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

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums is sorted in a strictly increasing order.

Hints/Notes

  • 2024/07/05
  • binary search tree
  • No solution from 0x3F

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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.size() == 0) {
            return nullptr;
        }
        int mid = nums.size() / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        if (mid >= 1) {
            vector<int> l = vector<int>(nums.begin(), nums.begin() + mid);
            root->left = sortedArrayToBST(l);
        }
        if (nums.size() - 1 >= mid + 1) {
            vector<int> r = vector<int>(nums.begin() + mid + 1, nums.end());
            root->right = sortedArrayToBST(r);
        }
        return root;
    }
};