## 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)

This comment has been removed by the author.

ReplyDeletevery smart solution. The key is to use reference in head node.

ReplyDeleteI 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 ?

ReplyDeleteHi Yu,

ReplyDeleteThough 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 '