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;    
    }
};

思路

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