Convert Sorted Array to Binary Search Tree Problem


Description

LeetCode Problem 108.

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

1
2
3
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,3] and [3,1] are both a height-balanced BSTs.

Constraints:

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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        if(num.size() == 0) return NULL;
        if(num.size() == 1) return new TreeNode(num[0]);
        
        int middle = num.size()/2;
        TreeNode* root = new TreeNode(num[middle]);
        
        vector<int> leftInts(num.begin(), num.begin()+middle);
        vector<int> rightInts(num.begin()+middle+1, num.end());
        
        root->left = sortedArrayToBST(leftInts);
        root->right = sortedArrayToBST(rightInts);
        
        return root;
    }
};




Related Posts

Convert Sorted Array to Binary Search Tree Problem

LeetCode 108. Given an integer array nums where the elements...

Validate Binary Search Tree Problem

LeetCode 98. Given the root of a binary tree, determine...

Same Tree Problem

LeetCode 100. Given the roots of two binary trees p...

Recover Binary Search Tree Problem

LeetCode 99. You are given the root of a binary...

Unique Binary Search Trees Problem

LeetCode 96. Given an integer n, return the number of...

Unique Binary Search Trees II Problem

LeetCode 95. Given an integer n, return all the structurally...