LeetCode 시리즈 의 "질서 있 는 링크 변환 이 진 트 리"

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

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

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

      0
     / \
   -3   9
   /   /
 -10  5

사고: 주어진 질서 있 는 링크 를 이 진 트 리 로 바 꾸 는 첫 번 째 단 계 는 루트 노드 를 확인 하 는 것 입 니 다.우 리 는 균형 잡 힌 이 진 트 리 를 구성 해 야 하기 때문에 비교적 직관 적 인 생각 은 뿌리 노드 왼쪽 나무 중의 노드 갯 수 와 오른쪽 나무 중의 노드 갯 수 를 가능 한 한 비슷 하 게 하 는 것 이다.이렇게 되면 좌우 자목 의 높이 도 매우 가 까 워 지고 고도 차 절대 치가 1 을 초과 하지 않 는 문제 의 요구 에 도달 할 수 있다.
구체 적 인 조작:

빠 르 고 느 린 지침 은 중간 노드 mid 를 찾 아 중간 노드 를 나무의 뿌리 노드 로 한다.

앞 뒤 지침 을 끊 고 앞 지침 에 대해 우 리 는 mid 의 앞 노드 를 유지 해 야 한다.그래서 빈 노드 를 만들어 야 합 니 다.

중 노드 slow 를 찾 은 후에 왼쪽 과 오른쪽 에 대해 똑 같은 조작 을 한다.

자바 구현 은 다음 과 같 습 니 다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
     
    public TreeNode sortedListToBST(ListNode head) {
     
        if(head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        ListNode mid = null;
        
        ListNode head2 = null;
        ListNode vHead1 = new ListNode(-1);
        vHead1.next = head;
        ListNode vHead2 = new ListNode(-2);
        ListNode pre = vHead1;

        while(fast.next != null && fast.next.next != null){
     
            pre = pre.next;
            slow = slow.next;
            fast = fast.next.next;
        }
        mid = slow;
        pre.next = null;
        vHead2 = mid.next;
        mid.next = null;

        TreeNode treeHead = new TreeNode(mid.val);
        if(vHead1.next != null) treeHead.left = sortedListToBST(vHead1.next);
        if(vHead2.next != null) treeHead.right = sortedListToBST(vHead2.next);
        return treeHead;
    }
}