Convert Sorted List to BST

Leave a comment

May 17, 2016 by oneOokay

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

基本上有两种想法:1.是找到中点recursively构建BST;2.用inorder traversal来做。

第一种:中点recursion:fast low指针找到中点;sortedListToBST本身作为recursion函数。但是由于fast slow指针while loop之后slow的位置,所以我们还需要slow之前的一个node,把node.next变成null,这样才能够进行下一次recursion。

时间复杂度为O(NlogN):每层递归一共访问N/2个节点,一共log N层递归(对应树的高度)。

public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while ( != null && != null){
            fast =;
            pre = slow;//pre指针用来标记slow前一个node
            slow =;
        TreeNode root = new TreeNode(slow.val);
        if (pre != null)
   = null;
        else {//此时可知左子树为null
            head = null;

        root.left = sortedListToBST(head);
        root.right = sortedListToBST(;
        return root;




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: