**Convert Sorted List to Binary Search Tree 将单链表表示为平

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

我想如果只是表示成二叉树，没有什么难度，，但是如果是表示为平衡二叉树那么可能就有难度了

要求左右子树的高度是均衡的

先给出自己的解法，很low，就是现将节点都保存在vector里面，在选用mid进行递归创建

时间，空间复杂度O(n)

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; *//** * Definition for binary tree * struct TreeNode { *int val; *TreeNode *left; *TreeNode *right; *TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:TreeNode *sortedListToBST(ListNode *head) {//<这里一开始想的时候就是觉得链表处理很不方便，希望能够先放到vector当中vector<TreeNode*> NodeList;if(head == NULL){return NULL;}TreeNode * phead = new TreeNode(head->val);NodeList.push_back(phead);while(head->next != NULL){head = head->next;TreeNode * node = new TreeNode(head->val);NodeList.push_back(node);}return BST(0,NodeList.size()-1,NodeList);//<表示初始值，和结束的值}TreeNode *BST(int start,int end,vector<TreeNode*> NodeList){if(start == end){return NodeList[start];}if((start+1) == end)//<按数值增大的方向排序，那么直接放在右孩子的位置{NodeList[start]->right = NodeList[end];return NodeList[start];}int Mid = (start+end)/2;TreeNode *root = NodeList[Mid];root->left = BST(start,Mid-1,NodeList);root->right = BST(Mid+1,end,NodeList);return root;}};下面是标准答案，时间复杂度就是O(N),空间复杂度为O(1)

但是在整个子树的递归过程中本人表示还是很绕啊

TreeNode *sortedListToBST(ListNode *head) {int len = 0;ListNode * node = head;while (node != NULL){node = node->next;len++;}return buildTree(head, 0, len-1);}TreeNode *buildTree(ListNode *&node, int start, int end){if (start > end) return NULL;int mid = start + (end – start)/2;TreeNode *left = buildTree(node, start, mid-1);TreeNode *root = new TreeNode(node->val); //<返回的时候表明上一层中start == mid,所以这个点为mid点root->left = left;node = node->next;root->right = buildTree(node, mid+1, end);return root;}

并且如此真实的活着——这，就是旅行的意义。