题目：
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:
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
把有序链表转换成 ：平衡二叉搜索树
解法一：使用快慢指针，找到中间节点；将链表分成两部分，递归构造二叉树
代码如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildBST(ListNode* head,ListNode* tail){if(head == tail)return NULL;ListNode* slow = head;ListNode* fast = head;while(fast != tail && fast->next != tail){slow = slow->next;fast = fast->next->next;}TreeNode* root = new TreeNode(slow->val);root->left = buildBST(head,slow);root->right = buildBST(slow->next,tail);return root;}TreeNode* sortedListToBST(ListNode* head) {if(head == NULL)return NULL;return buildBST(head,NULL);}
};
解法二：将有序链表转换成有序数组，按照上题，通过有序数组构造二叉树的方法构造二叉树，代码复杂度O（n），比解法一的代码复杂度O（nlogn）要低
代码如下：
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& nums,int left,int right){if(left > right)return NULL;int mid = left + (right - left)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = buildTree(nums,left,mid-1);root->right = buildTree(nums,mid+1,right);return root;}TreeNode* sortedListToBST(ListNode* head) {vector<int> ListToArray;if(head == NULL)return NULL;while(head != NULL){ListToArray.push_back(head->val);head = head->next;}return buildTree(ListToArray,0,ListToArray.size()-1);}
};