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)
