从排序的链表创建平衡二叉搜索树

自下而上创建节点如何？

该解决方案的时间复杂度为O（N）。我的博客文章中的详细说明：

http://www.leetpre.com/2010/11/convert-sorted-list-to-balanced-
binary.html

我们只需要遍历链接列表两次即可。首先遍历以获取列表的长度（然后将其作为参数n传递到函数中），然后按照列表的顺序创建节点。

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {  if (start > end) return NULL;  // same as (start+end)/2, avoids overflow  int mid = start + (end - start) / 2;  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);  BinaryTree *parent = new BinaryTree(list->data);  parent->left = leftChild;  list = list->next;  parent->right = sortedListToBST(list, mid+1, end);  return parent;}BinaryTree* sortedListToBST(ListNode *head, int n) {  return sortedListToBST(head, 0, n-1);}