EEPW论坛

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

题意;将排序链表转换成平衡二叉树；

每次取中间节点，自然就是平衡二叉树了；

思路：自顶向下递归解决，先找到中间节点作为根节点，然后递归左右两部分，所以我们先需要连找到中间节点，对于单链表来说，

必须要遍历一遍，可以使用快慢指针加速查找速度；

1. class Solution {  

2. public:  

3.     TreeNode* sortedListToBST(ListNode* head)  

4.     {  

5.         if (head==NULL)  

6.         {  

7.             return NULL;  

8.         }  

9.   

10.         //用快慢指针来找中间节点  

11.         ListNode* slow = head;  

12.         ListNode* fast = head;  

13.         ListNode* preSlow = NULL;  

14.   

15.         while (fast!=NULL && fast->next!=NULL)  

16.         {  

17.             preSlow = slow;  

18.             slow = slow->next;  

19.             fast = fast->next->next;  

20.         }  

21.   

22.         TreeNode* mid = new TreeNode(slow->val);  

23.         //分别递归左右部分  

24.         if (preSlow!=NULL)  

25.         {  

26.             preSlow->next = NULL;  

27.             mid->left = sortedListToBST(head);  

28.         }  

29.   

30.         if (slow->next!=NULL)  

31.         {  

32.             mid->right = sortedListToBST(slow->next);  

33.         }  

34.   

35.         return mid;  

36.     }  

37. };