将有序的单链接列表转换为平衡的二进制搜索树

给出升序的有序单链列表，将其转换为平衡的二进制搜索树.

单链表的节点结构如下.

struct node {
     int data; 
     struct node *next；
}；

由于单链列表是按升序排列的，因此您可以参考上一篇文章，将有序数组转换为平衡的二进制搜索树. 链表中节点的值首先存储在数组中，然后以相同的方式实现平衡二叉排序树，时间复杂度为O（N）. 当然，不必额外使用数组来保存节点值，但是每次递归时都需要找到链表的中间元素，因为每次查找中间元素都需要O（N / 2 ）时间，总共搜索为O（lgN），所以总时间为O（NlgN）.

我们可以使用自下而上的方法，不再需要每次都查找中间元素. 以下代码仍然需要链表的长度作为参数，计算链表长度的时间复杂度为O（N）平衡二叉排序树，转换算法的时间复杂度也为O（N），因此总和时间复杂度为O（N）.

BinaryTree* sortedListToBST(struct node*& 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(struct node *head, int n) {
  return sortedListToBST(head, 0, n-1);
}

应该在代码中指出，每次调用sortedListToBST函数时，列表的位置都会改变. 调用该函数后，列表始终指向mid + 1的位置（如果满足返回条件，则列表的位置将不会更改）.

例如，如果链接列表只有两个节点3-> 5-> NULL，则初始开始= 0，结束=1. 然后mid = 0，然后递归调用sortedListToBST（列表，开始，中间1） ），然后直接返回NULL. 也就是说，左子节点为NULL，根节点为3，然后链表列表指向5，然后调用sortedListToBST（list，mid + 1，end），此调用返回节点5并将其分配给根节点3的权限. child. 此呼叫的中= 1，呼叫完成后，列表已指向链接列表的末尾.

英文地址将排序列表转换为平衡的二进制搜索树

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-179509-1.html