从有序链表创建平衡的二叉搜索树
从排序的单链表创建平衡的二进制搜索树的最佳方法是什么？
回答 9
Stack Overflow用户
发布于 2010-11-30 10:02:34
自下而上创建节点如何？
该方案的时间复杂度为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);
}Stack Overflow用户
发布于 2010-11-21 05:18:56
你不能做得比线性时间更好，因为你至少必须读取列表的所有元素，所以你最好将列表复制到一个数组中(线性时间)，然后以通常的方式高效地构建树，例如，如果你有9, 12，18 , 23 , 24 , 51 ,84这个列表，那么你应该从23作为根，12和51的孩子，然后9和18成为12的孩子，24和84成为51的孩子。总体而言，如果你做得对，应该是O(n)。
实际的算法是“将列表的中间元素作为根元素，递归地为中间元素左侧和右侧的子列表构建BST，并将它们附加在根元素的下面”。
Stack Overflow用户
发布于 2010-11-21 05:30:04
Best不仅仅是异步运行时。排序后的链表包含了直接创建二叉树所需的所有信息，我认为这可能就是他们想要的
请注意，第一个和第三个条目成为第二个条目的子节点，然后第四个节点具有第二个和第六个节点的孩子(具有第五个和第七个孩子)，依此类推……
用psuedo代码
read three elements, make a node from them, mark as level 1, push on stack
loop
read three elemeents and make a node of them
mark as level 1
push on stack
loop while top two enties on stack have same level (n)
make node of top two entries, mark as level n + 1, push on stack
while elements remain in list(当剩下的元素少于三个或任何点上有一棵不平衡的树时，需要进行一些调整)
编辑：
在任何点上，堆栈上都有一个高度为N的左侧节点。下一步是读取一个元素，然后读取并在堆栈上构造另一个高度为N的节点。要构造一个高度为N的节点，在堆栈上创建并推送一个高度为N-1的节点，然后读取一个元素，在堆栈上创建另一个高度为N -1的节点--这是一个递归调用。
实际上，这意味着算法(即使经过修改)也不会生成平衡树。如果有2N+1节点，它将生成一个树，左侧有2N-1个值，右侧有1个值。
所以我认为@sgolodetz的答案更好，除非我能想出一种在构建时重新平衡树的方法。
https://stackoverflow.com/questions/4235013
复制相似问题