링크 - 109. 질서 있 는 링크 전환 고도 균형 이 진 트 리

제목:
단일 체인 표를 지정 합 니 다. 그 중의 요 소 는 오름차 순 으로 정렬 하여 고도 의 균형 을 가 진 이 진 검색 트 리 로 변환 합 니 다.
이 문제 에서 고도 균형 이 진 트 리 는 이 진 트 리 의 각 노드 를 가리킨다. 의 좌우 두 나무의 높이 차 는 절대 1 을 초과 하지 않 는 다.
예 를 들 면:

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

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

      0
     / \
   -3   9
   /   /
 -10  5

방법:
병합 정렬 과 마찬가지 로 매번 중간 값 을 노드 로 선택 하고 노드 의 왼쪽 트 리 범 위 는 좌표 0 에서 중간 값 좌표 - 1 이 며 오른쪽 트 리 는 중간 값 좌표 + 1 에서 끝까지 이다.
상기 과정 에서 머리 노드 가 끝 노드 보다 클 때 까지 반복 합 니 다.

/**
 * 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 {
public:
    int getLength(ListNode* l){
        int cnt=0;
        while(l){
            l=l->next;
            cnt++;
        }
        return cnt;
    }

    TreeNode* Sort(TreeNode* t,int *a,int start,int tail){
            if(start<=tail){
                int mid=(start+tail)/2;
                t=new TreeNode(a[mid]);
                t->left=Sort(t->left,a,start,mid-1);
                t->right=Sort(t->right,a,mid+1,tail);
            }
            return t;
    }

    TreeNode* sortedListToBST(ListNode* head) {
            ListNode* tmp=head;
            int cnt=getLength(tmp),i=0;
             if(!cnt)  return NULL;
            
            int a[cnt];
            while(head){
                a[i++]=head->val;
                head=head->next;
            }
            
            TreeNode* t;
            return Sort(t,a,0,cnt-1);
    }
};