(Leet Code c++)Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

Easy

4312293Add to ListShare

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:

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

 

Constraints:

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

정렬된 배열을 BST로 바꿔야 한다.

재귀를 통해 BST를 쉽게 만들 수 있다.

/**
 * 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 * makeTree(vector<int> nums, int start, int end){
        if(start > end){
            return NULL;
        }
        
        int mid = (start + end) / 2;
        TreeNode * root = new TreeNode(nums[mid]);
        root->left = makeTree(nums, start, mid - 1);
        root->right = makeTree(nums, mid + 1, end);
        
        return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int start = 0;
        int end = nums.size() - 1;
        
        return makeTree(nums, start, end);
    }
};