https://www.cnblogs.com/hellowooorld/p/6624709.html

题目

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

1
2
3
4
5
6
7
8
9
Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3 9
/ /
-10 5

大意

给定一个链表,生成一个二叉平衡树.

答案

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
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head)
{
//利用fast 和 slow 指针 找到链表中点
return build(head,NULL);
}
//两个参数分别是链表中左节点的指针,右节点的下一个的指针.
TreeNode* build(ListNode* start, ListNode* end)
{
if (start == end)
{
return NULL;
}
ListNode* fast = start;
ListNode* slow = start;
while (fast != end && fast->next != end)//注意第一次执行的时候end为NULL 没毛病。。
{
fast = fast->next->next;
slow = slow->next;
}
TreeNode* node = new TreeNode(slow->val);
node->left = build(start, slow);
node->right = build(slow->next, end);
return node;
}
};

思路

利用快慢指针找到中间节点,作为根节点,然后左子树即为左边链表部分,右子树即为右边链表部分,递归进行即可。