108. Convert Sorted Array to Binary Search Tree

주어진 정렬된 정수 배열을 사용하여 균형 잡힌 이진 검색 트리(Binary Search Tree)를 만드는 문제입니다. 아래는 문제의 자세한 설명입니다:

문제 설명:

주어진 정렬된 정수 배열 nums를 사용하여 높이 균형을 갖는 이진 검색 트리를 생성하세요. 이진 검색 트리는 다음과 같은 조건을 만족해야 합니다:

노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값의 노드들만 포함되어야 합니다.
노드의 오른쪽 서브 트리에는 해당 노드보다 큰 값의 노드들만 포함되어야 합니다.
각 서브 트리도 이진 검색 트리여야 합니다.
예시:

주어진 nums 배열이 [1, 2, 3]라면, 다음과 같은 이진 검색 트리를 생성해야 합니다:

    2
   / \
  1   3

노트:

nums 배열의 길이는 1 이상 10^4 이하입니다.
nums 배열은 오름차순으로 정렬되어 있습니다.
이 문제를 해결하기 위해 다음과 같은 단계를 따를 수 있습니다:

주어진 정렬된 배열에서 중간 원소를 찾아 루트 노드로 만듭니다.
중간 원소를 기준으로 왼쪽 서브 배열과 오른쪽 서브 배열로 나눕니다.
왼쪽 서브 배열에 대해 재귀적으로 균형 잡힌 이진 검색 트리를 생성합니다.
오른쪽 서브 배열에 대해 재귀적으로 균형 잡힌 이진 검색 트리를 생성합니다.
왼쪽 서브 트리와 오른쪽 서브 트리를 루트 노드의 왼쪽 및 오른쪽 자식으로 연결합니다.
이러한 방법을 사용하여 주어진 정렬된 배열을 균형 잡힌 이진 검색 트리로 변환할 수 있습니다.

   TreeNode* sortedArrayToBST(vector<int>& nums) {
         return sortedArrayToBST(nums, 0, nums.size() - 1);
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sortedArrayToBST(nums, left, mid - 1);
        root->right = sortedArrayToBST(nums, mid + 1, right);
        return root;  
    }