leetcode Question 24: Convert Sorted List to Binary Search Tree

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.



Analysis:



The easier way to solve this problem is use the idea as the previous one.
Here present another way of thinking.
In the previous array to BST, we construct the BST in a top-down way. For the list data structure, to get the mid point every time is a waster of time. So construct the BST in a bottom-up way. However, the length of the list must be computed.

Recursively 
1. construct the left tree 
2. construct the root node, list pointer +1.
3. construct the right node

Note that in Python, the function argument is more like a "pass by value" way if the argument is immutable, to use the C++ like "pass by reference", the argument should be a mutable type, here in the code, a list of "ListNode" is used.

Code(C++):





/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    TreeNode *l2bst(ListNode* &head,int st, int ed){
        if (st>ed) {return NULL;}
        TreeNode *lefttree = l2bst(head,st,int(st+(ed-st)/2)-1);
        TreeNode *parent = new TreeNode(head->val); 
        head = head->next;
        TreeNode *righttree = l2bst(head,int(st+(ed-st)/2)+1,ed);
        parent->left  = lefttree;
        parent->right  = righttree;
        return parent;
    }
    
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (head==NULL){return NULL;}
        ListNode *h=head;
        int len = 0;
        while (h){
            len = len+1;
            h = h->next;
        }
        TreeNode *root=l2bst(head,1,len);
        return root;

    }
};


Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a list node
    # @return a tree node
    def bst(self, head, st, ed):
        if st > ed or head[0] == None:
            return None
        mid = st + (ed - st)/2
        left = self.bst(head, st, mid - 1)
        root = TreeNode(head[0].val)
        head[0] = head[0].next
        right = self.bst(head, mid + 1, ed)
        root.left = left
        root.right = right
        return root

    def sortedListToBST(self, head):
        if head == None: 
            return None
        tmp = head
        n = 0
        while tmp != None:
            n += 1
            tmp = tmp.next
        return self.bst([head], 0, n)
        
        
        

4 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. very smart solution. The key is to use reference in head node.

    ReplyDelete
  3. I found the middle point of the list by using two pointers, one moving one step ahead and the other moving 2 steps ahead each time, and then used two recursive calls, for the left and the right subtree respectively. But that solution is O(nlog(n)) and this is O(n), right ?

    ReplyDelete
  4. Hi Yu,

    Though the two approaches (one is yours and one is top to bottom approach) complexities are O(n) and O(nlog(n)) respectively, I test both approaches in Leetcode several times, each cost similar amount of time, the bottom up approach actually costs slight more, do you know the reason why '

    ReplyDelete