算法1

() $O(n)$

用有序数组构造一个平衡的二叉搜索树

时间复杂度

参考文献

java代码

/**
 * 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;
        //先把链表转成数组
        ArrayList<Integer> arr = new ArrayList<>();
        while(head!=null)
        {
            arr.add(head.val);
            head  = head.next;
        }
        //arr现在是有序数组并且是个中序遍历
        return bT(0,arr.size()-1,arr);
    }
    public TreeNode bT(int l,int r,ArrayList<Integer> arr){
        if(l==r) return new TreeNode(arr.get(l)); 
        int m = l+r>>1;
        TreeNode root = new TreeNode(arr.get(m));
        if(m-1>=l) root.left = bT(l,m-1,arr);
        if(m+1<=r) root.right = bT(m+1,r,arr);
        return root;
    }
}

算法2

() $O(n)$

不借助数组

时间复杂度

参考文献

java代码

/**
 * 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;
        return dfs(head);
    }
    public TreeNode dfs(ListNode head){
        if(head==null) return null;
        if(head.next==null) return new TreeNode(head.val);
        //找到链表的中间数，然后将链表断开成左子树和根节点和右子树
        ListNode p = head;
        ListNode q = head;
        ListNode pre = null;
        while(q!=null&&q.next!=null)
        {
            pre =p;
            p=p.next;
            q=q.next.next;
        }
         pre.next=null;
        TreeNode root =new TreeNode(p.val);
        root.left = dfs(head);
        root.right= dfs(p.next);
        return root;
    }
}