NO CODING NO LIFE: Lintcode: 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.

Have you met this question in a real interview?

Yes

Example

               2
1->2->3  =>   / \
             1   3

Tags Expand

Recursion Linked List

Similar to convert array to binary search tree:
http://codinggamestart.blogspot.com/2015/10/converted-sorted-array-to-binary-search.html

Solution:

In general, we use top to bottom way to create binary search tree.

However, in this problem, the input is linked list, we need O(n) to look for each node, not a good one.

Another way to create binary search tree is to create from the bottom to top, kind of hard to understand, but efficient for linked list.

Create the binary search tree recursively. The key is to reference the head pointer as input parameter.

1. construct the left tree

2. construct the root, head pointer + 1

3. construct the right tree

4. return root

Time: O(n)

Stack Space:O(logn)

p.s. The best way to understand this algorithm is to run it by hands, e,g, use 0 --> 1 --> 2 --> 3 --> 4

Reference:

http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html

http://articles.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

http://yucoding.blogspot.com/2012/12/leetcode-question-24-convert-sorted.html

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    TreeNode *sortedListToBST(ListNode *head) {
        int len = 0;
        ListNode *cur = head;
        while(cur){
            len++;
            cur = cur->next;
        }
        return sortedListToBST(head, 0, len - 1);
    }
    TreeNode* sortedListToBST(ListNode* &head, int start, int end){
        if(start > end) return NULL;
        int mid = start + (end - start) / 2;
        TreeNode* left = sortedListToBST(head, start, mid - 1);
        TreeNode* root = new TreeNode(head->val);
        head = head->next;
        TreeNode* right = sortedListToBST(head, mid + 1, end);
        root->left = left;
        root->right = right;
        return root;
    }
};

NO CODING NO LIFE

2015年9月1日星期二

Lintcode: Convert Sorted List to Binary Search Tree

没有评论:

发表评论