通过本文主要向大家介绍了lintcode平衡二叉树,lintcode,lintcode官网,lintcode答案,lintcode爬楼梯等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
您在真实的面试中是否遇到过这个题？
分析：就是一个简单的递归，只是需要有些链表的操作而已
代码：
/**
* 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;
}
}
};
</div>
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
</div>