给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
您在真实的面试中是否遇到过这个题？
分析：就是一个简单的递归，只是需要有些链表的操作而已
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
/**
* 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;
}
}
};
|
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/wangyuquanliuli/article/details/47359405