从已排序的链接列表创建平衡二进制搜索树

Question

从排序的单链表创建平衡二叉搜索树的最佳方法是什么？

Answer 1

自下而上创建节点怎么样？

该解决方案的时间复杂度为O(N).我博客文章中的详细说明:

http://www.leetcode.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);
}