[LeetCode]109. 질서정연 체인표 변환 두 갈래 검색 트리

제목

요소는 오름차순으로 정렬되고 고도로 균형 잡힌 BST로 변환되는 셀 체인 테이블을 지정합니다.이 문제에 대해 고도의 균형이 잡힌 두 갈래 나무는 그 중에서 각 노드의 두 개의 하위 나무의 깊이 차이가 1을 넘지 않는 두 갈래 나무를 가리킨다.   :

 ： [-10, -3, 0, 5, 9],

 ：[0, -3, 9, -10, null, 5]

      0
     / \
   -3   9
   /   /
 -10  5

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode* sortedChild(ListNode* head, ListNode* tail)
    {
        if (head == tail)
            return NULL;
        if (head->next==tail)
        {
            // 
            TreeNode* root = new TreeNode(head->val);
            return root;
        }
        ListNode* mid = head, *temp = head;
        //-------------------- Begin-----------------------
        while (temp!=tail&&temp->next!=tail)
        {
            // , 2 , mid , 
            mid = mid->next;
            temp = temp->next->next;
        }
        //-------------------- End-----------------------
        TreeNode* root = new TreeNode(mid->val);
        root->left = sortedChild(head, mid);
        root->right = sortedChild(mid->next, tail);
        return root;
    }
public:
    TreeNode * sortedListToBST(ListNode* head)
    {
        return sortedChild(head, NULL);
    }
};

알고리즘 사고방식

위에서 제시한 것은 내가 매우 완벽한 해법이라고 생각한다. 말하자면 부끄럽다. 이 문제는 내가 사고방식에서 대체적으로 같다. 모두 매번 중위치를 찾아 결점을 삽입하는 것이다. 이 해법의 정수는 바로 그것 의 사상에 있다. 두 개의 지침을 통해 앞걸음수를 1과 2로 설정하여 중간 위치를 찾는 것이다. 기록하고 배울 만하다.많은 나무와 체인 테이블의 알고리즘에서 이 중간값 찾기 사상이 모두 사용될 수 있다고 믿습니다. 이에 기록하고, 그 밖에 전진의 판단 조건에 주의해야 합니다!이 문제와 관련된 것은 109. 이다. 이 문제는 더욱 간단한 문제이다. 수조는 Random Access이기 때문에 우리는 O(1) 시간에 중간값을 얻을 수 있다.
다음으로 전송:https://www.cnblogs.com/lizhenghao126/p/11053690.html