LintCode sorted list converted to binary search tree analysis and examples
- 2020-05-19 05:16:58
- OfStack
Given a single linked list of all elements in ascending order, convert it into a highly balanced two-point lookup tree
Have you ever been asked this question in a real interview?
Analysis: is a simple recursion, just need some linked list operations
Code:
/**
* 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) {
// write your code here
if(head==nullptr)
return nullptr;
int len = 0;
ListNode*temp = head;
while(temp){len++;temp = temp->next;};
if(len==1)
{
return new TreeNode(head->val);
}
else if(len==2)
{
TreeNode*root = new TreeNode(head->val);
root->right = new TreeNode(head->next->val);
return root;
}
else
{
len/=2;
temp = head;
int cnt = 0;
while(cnt<len)
{
temp = temp->next;
cnt++;
}
ListNode*pre = head;
while(pre->next!=temp)
pre = pre->next;
pre->next = nullptr;
TreeNode*root = new TreeNode(temp->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(temp->next);
return root;
}
}
};
Thank you for reading, I hope to help you, thank you for your support of this site!