C++LeetCode 구현(109.질서 있 는 링크 를 이 진 트 리 로 변환)

[LeetCode]109.Convert Sorted List to Binary Search Tree 질서 있 는 링크 를 이 진 트 리 로 변환 합 니 다.
Given a singly linked list 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 every node never differ by more than 1.
Example:
Given the sorted linked list: [-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
이 문 제 는 질서 있 는 링크 를 이 진 트 리 로 바 꾸 고 이전 과 바 꾸 라 는 것 이다.  Convert Sorted Array to Binary Search Tree  사고방식 은 완전히 같다.단지 조작의 데이터 유형 에 차이 가 있 을 뿐이다.하 나 는 수조 이 고 하 나 는 체인 테이블 이다.배열 이 편리 하면 index 를 통 해 임의의 요 소 를 직접 방문 할 수 있 지만 링크 는 안 됩 니 다.2 분 검색 법 은 매번 중심 점 을 찾 아야 하기 때문에 링크 의 중간 점 을 찾 는 것 은 빠 른 속도 지침 을 통 해 조작 할 수 있 고 앞의 두 블 로 그 를 참조 할 수 있다.  Reorder List  화해시키다  Linked List Cycle II  속도 지침 에 대한 응용.중심 점 을 찾 은 후에 중심 점 의 값 으로 하나의 수의 뿌리 노드 를 만 든 다음 에 원래 의 링크 를 끊 고 앞 뒤 두 개의 링크 로 나 누 어야 한다.모두 원래 의 노드 를 포함 하지 못 한 다음 에 이 두 개의 링크 에 대해 원래 의 함 수 를 재 귀적 으로 호출 하고 각각 왼쪽 과 오른쪽 노드 를 연결 하면 된다.코드 는 다음 과 같 습 니 다:
해법 1:

class Solution {
public:
    TreeNode *sortedListToBST(ListNode* head) {
        if (!head) return NULL;
        if (!head->next) return new TreeNode(head->val);
        ListNode *slow = head, *fast = head, *last = slow;
        while (fast->next && fast->next->next) {
            last = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        last->next = NULL;
        TreeNode *cur = new TreeNode(slow->val);
        if (head != slow) cur->left = sortedListToBST(head);
        cur->right = sortedListToBST(fast);
        return cur;
    }
};

우 리 는 다음 과 같은 재 귀 방법 을 사용 하여 재 귀 함 수 를 다시 쓸 수 있 습 니 다.두 개의 입력 매개 변수 가 있 습 니 다.서브 링크 의 출발점 과 종점 이 있 습 니 다.이 두 가지 점 을 알 았 기 때문에 링크 의 범 위 는 확정 할 수 있 습 니 다.중간 부분 을 이 진 검색 트 리 로 직접 전환 하면 됩 니 다.재 귀 함수 중의 내용 은 위의 해법 과 매우 비슷 합 니 다.참조 코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (!head) return NULL;
        return helper(head, NULL);
    }
    TreeNode* helper(ListNode* head, ListNode* tail) {
        if (head == tail) return NULL;
        ListNode *slow = head, *fast = head;
        while (fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        TreeNode *cur = new TreeNode(slow->val);
        cur->left = helper(head, slow);
        cur->right = helper(slow->next, tail);
        return cur;
    }
};

유사 한 제목:
Convert Sorted Array to Binary Search Tree
참고 자료:
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise.
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35470/Recursive-BST-construction-using-slow-fast-traversal-on-linked-list
여기 서 C++구현 LeetCode(109.질서 있 는 링크 를 이 진 트 리 로 전환)에 관 한 글 을 소개 합 니 다.더 많은 관련 C++구현 질서 있 는 링크 를 이 진 트 리 로 전환 하 는 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부탁드립니다!