109. Convert Sorted List to Binary Search Tree
C++，代码很简短。。。本来可以真的去构造AVL树，但是给的序列已经是有序的了，就没必要了。不然AVL写下来至少也得七八十行。。。
思路就是利用分治的思想，将中间结点作为分割点，分成左子树和右子树。
- 首先链表元素可以先用
vector存一下，因为后面如果用链表再去找中间结点的话，很影响效率； - 找到当前区间
[left, right]的中间结点mid，构造为根结点； - 然后再递归地构造根结点的左子树和右子树；
- 最后记得返回根结点。
代码如下：
typedef TreeNode* TNP;
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
vector<int> list;
ListNode *p = head;
while (p) {
list.push_back(p->val);
p = p->next;
}
return pre(0, list.size() - 1, list);
}
TNP pre(int left, int right, vector<int> &list) {
if (left > right) return NULL;
int mid = (left + right) / 2;
TNP root = new TreeNode(list[mid]);
root->left = pre(left, mid - 1, list);
root->right = pre(mid + 1, right, list);
return root;
}
};
