108. Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Convert Sorted Array to Binary Search Tree - LeetCode

 

어제 풀었던 111과 같은 easy인데 난이도는 조금 다른듯.

오름차순으로 정렬된 정수의 벡터를 인수로 받았을 때 binary search tree로 변경해 출력하는 문제다.

 

데이터 자체는 정렬되어 있으므로 데이터 목록을 재귀적으로 반씩 나누어가며 left와 right 노드를 채워가면 되겠다.

 

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