C++LeetCode 구현(108.질서 있 는 배열 을 두 갈래 검색 트 리 로 변환)

[LeetCode]108.Convert Sorted Array to Binary Search Tree 질서 있 는 배열 을 이 진 트 리 로 변환 합 니 다.
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of everynode never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
      0
/ \
-3   9
/   /
-10  5 
이 문 제 는 질서 있 는 배열 을 이 진 트 리 로 바 꾸 는 것 입 니 다.이 진 트 리 라 는 것 은 왼쪽<뿌리<오른쪽 특성 을 만족 시 키 는 것 입 니 다.이 진 트 리 를 중간 순서 로 옮 겨 다 니 면 질서 있 는 배열 을 얻 을 수 있 습 니 다.그러면 반대로 우 리 는 뿌리 노드 가 질서 있 는 배열 의 중간 점 이 어야 한 다 는 것 을 알 수 있다.중간 점 에서 좌우 두 개의 질서 있 는 배열 로 나 뉘 어 그 중에서 간 점 을 원래 중간 점 의 좌우 두 개의 노드 로 찾 는 것 이 바로 이분 검색 법의 핵심 사상 이 아니 냐 는 것 을 알 수 있다.그래서 이 문 제 는 바로 이분 검색 법 입 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0 , (int)nums.size() - 1);
    }
    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int mid = left + (right - left) / 2;
        TreeNode *cur = new TreeNode(nums[mid]);
        cur->left = helper(nums, left, mid - 1);
        cur->right = helper(nums, mid + 1, right);
        return cur;
    }
};

우 리 는 추가 재 귀 함 수 를 사용 하지 않 고 원 함수 에서 재 귀 를 완성 할 수 있 습 니 다.원 함수 의 매개 변 수 는 하나의 배열 이기 때문에 입력 배열 의 중간 숫자 를 꺼 낸 후에 모든 양 끝 의 배열 을 새로운 배열 로 구성 하고 재 귀 함 수 를 각각 호출 하 며 새로 만 든 cur 결점 의 좌우 부분 결점 에 연결 해 야 합 니 다.참조 코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) return NULL;
        int mid = nums.size() / 2;
        TreeNode *cur = new TreeNode(nums[mid]);
        vector<int> left(nums.begin(), nums.begin() + mid), right(nums.begin() + mid + 1, nums.end());
        cur->left = sortedArrayToBST(left);
        cur->right = sortedArrayToBST(right);
        return cur;
    }
};

유사 한 제목:
Convert Sorted List to Binary Search Tree
참고 자료:
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35220/My-Accepted-Java-Solution
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/35394/6-lines-Java-Accepted-Solution
여기 서 C++구현 LeetCode(108.질서 있 는 배열 을 이 진 트 리 로 전환)에 관 한 글 을 소개 합 니 다.더 많은 관련 C++구현 질서 있 는 배열 을 이 진 트 리 로 전환 하 는 내용 은 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부탁드립니다!