题目描述
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
题解
链表，相比于上一题的数组，有什么区别呢？不好找节点了啊……
用两个指针，一块一慢，快的每次走两步，慢的每次走一步，这样当快指针遍历结束时，慢指针指向的也就是链表的中间位置。这时候把中间位置的结点的值作为二叉搜索树当前结点的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| TreeNode* ListToBST(ListNode* head, ListNode* tail){
if (head==tail)return NULL;
if (head->next==tail)return new TreeNode(head->val);
ListNode *p, *q;
p = head; q = head;
while (q != tail) {
if (q->next == tail)break;
p = p->next;
q = q->next->next;
}
TreeNode* root = new TreeNode(p->val);
root->left = ListToBST(head, p);
root->right = ListToBST(p->next, tail);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
if (!head)return NULL;
if (!head->next)return new TreeNode(head->val);
return ListToBST(head, NULL);
}
|
要学会用双指针。改的好看点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| TreeNode* ListToBST(ListNode* head, ListNode* tail)
{
if (head==tail)return NULL;
ListNode *p, *q;
p = head; q = head;
while (q!=tail&&q->next!=tail){
p = p->next;
q = q->next->next;
}
TreeNode* root = new TreeNode(p->val);
root->left = ListToBST(head, p);
root->right = ListToBST(p->next, tail);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
return ListToBST(head, NULL);
}
|
不过上面的代码效率也太低了，去学个好的来。空间换时间？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| TreeNode* sortedListToBST(ListNode* head) {
vector<int> v;
while(head != nullptr){
v.push_back(head->val);
head = head->next;
}
return buildTree(v, 0, v.size());
}
TreeNode * buildTree(vector<int> & v, int begin, int end){
if(begin == end) return nullptr;
int middle = (begin+end)/2;
TreeNode * root = new TreeNode(v[middle]);
root->left = buildTree(v, begin, middle);
root->right = buildTree(v, middle+1, end);
return root;
}
|
https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/solution/c-2chong-jie-fa-bu-yong-duan-kai-lian-biao-by-alex/
还是慢。那就不是我的问题了。
偷懒了好几天实在抱歉，从今天开始继续吧。