Convert Sorted List to Binary Search Tree

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

http://www.lintcode.com/en/problem/convert-sorted-list-to-binary-search-tree/

Discussion

跟Convert Sorted Array to Balanced Binary Search Tree类似，只是list不能random access，也就是说不能用O(1)的时间access element。但是可以借鉴它的思想：分治，自定向下的构建BST，只是要花费O(logn)的时间找到一个元素，所以是O(n log n) runtime, O(log n) stack space。

Solution

最简单是用list构建一个array，这样就可以完全调用Array to BST的方法。

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    TreeNode *sortedListToBST(ListNode *head) {
        // write your code here
        vector<int> A;
        while(head != NULL) {
            A.push_back(head->val);
            head = head->next;
        }
        if(A.size() == 0) return NULL;
        return bst(A, 0, A.size()-1);
    }
private:
    TreeNode *bst(vector<int> A, int start, int end) {
        if (start > end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *root = new TreeNode(A[mid]);
        root->left = bst(A, start, mid-1);
        root->right = bst(A, mid+1, end);
        return root;
    }
};

借鉴array to BST的思想，divide and conquer：

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    TreeNode *sortedListToBST(ListNode *head) {
        // write your code here
        ListNode *tmp = head;
        int len = 0;
        while(head != NULL) {
            len++;
            head = head->next;
        }
        if(len == 0) return NULL;
        head = tmp;
        return bst(head, 0, len-1);
    }
private:
    TreeNode *bst(ListNode *head, int start, int end) {
        if (start > end) return NULL;
        int mid = start + (end-start)/2;
        ListNode *midNode = head;
        for(int i=0; i<mid; i++) {
            midNode = midNode->next;
        }
        TreeNode *root = new TreeNode(midNode->val);
        root->left = bst(head, start, mid-1);
        root->right = bst(head, mid+1, end);
        return root;
    }
};

上面的code用brute force查找链表中的某个元素，每次都从head开始找，O(n)的查找时间。O(n^2) runtime。提交的时候会超时。

改进方法是不要每次都从head开始找，根节点是从头开始找到mid，是n/2, 孩子节点不要从头找了，这样可以用n/4的时间找到，以此类推，可以花费O(longn)的查找时间，所以是O(nlongn) runtime.

只需要将root->right = bst(head, mid+1, end);改为root->right = bst(midNode->next, 0, end-mid-1);就可以了。

还有个bottom-up方法，时间复杂度O(n)，空间复杂度O(logn)，没有看懂。。。。

TreeNode *sortedListToBSTHelper(ListNode **head, int start, int end) {
        if(start > end) return NULL;
        int mid = start + (end - start) / 2;
        TreeNode *left = sortedListToBSTHelper(head, start, mid-1);
        TreeNode *node = new TreeNode((*head)->val);
        (*head) = (*head)->next;
        node->left = left;
        node->right = sortedListToBSTHelper(head, mid+1, end);
        return node;
    }

Solution: another way to find mid in list - fast-low pointer

也是O(nlogn) runtime

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head)
    {
        return sortedListToBST( head, NULL );
    }

private:
    TreeNode *sortedListToBST(ListNode *head, ListNode *tail)
    {
        if( head == tail )
            return NULL;
        if( head->next == tail )    // 这里也可以不要
        {   
            TreeNode *root = new TreeNode( head->val );
            return root;
        }
        ListNode *mid = head, *temp = head;
        while( temp != tail && temp->next != tail )    // 寻找中间节点
        {
            mid = mid->next;
            temp = temp->next->next;
        }
        TreeNode *root = new TreeNode( mid->val );
        root->left = sortedListToBST( head, mid );
        root->right = sortedListToBST( mid->next, tail );
        return root;
    }
};