단일 체인 테이블을 지정합니다. 그 중의 요소는 오름차순으로 정렬됩니다. 이를 균형 두 갈래 검색 트리(BST)로 바꾸십시오

귀속:o(nlogn)

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     *
     * @param head ListNode 
     * @return TreeNode 
     */
    // 
    public ListNode getmid(ListNode head){
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre_slow=null;// slow 
        // 
        while(fast!=null&&fast.next!=null){
            pre_slow=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        if(pre_slow!=null)   pre_slow.next=null;// 
        return slow;
    }
    public TreeNode sortedListToBST (ListNode head) {
        if(head==null){
            return null;
        }
        ListNode mid=this.getmid(head);
        // 
       TreeNode node=new TreeNode(mid.val);
       // ， node
       if(head==mid){
           return node;
       }
       node.left=sortedListToBST(head);
       node.right=sortedListToBST(mid.next);
       return node;
    }
}

오름차순 정렬된 그룹을 제공하여 균형 두 갈래 검색 트리(BST)로 변환

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    /**
     *
     * @param num int 
     * @return TreeNode 
     */
    public TreeNode getBST(int[]num,int left,int right){
        if(num==null ||num.length<=0|| left>right){
            return null;
        }
// 
        int mid=left+(right-left+1)/2;
        // 
        if(left==right){
            return new TreeNode(num[left]);
        }
        // 
        TreeNode root=new TreeNode(num[mid]) ;
        // 
        root.left=getBST(num,left,mid-1);
        // 
        root.right=getBST(num,mid+1,right);
        return root;
    }
    public TreeNode sortedArrayToBST (int[] num) {
        if(num==null ||num.length==0){
            return null;
        }
        return getBST(num,0,num.length-1);
    }
}