从排序链表创建平衡二叉搜索树 [英] Create Balanced Binary Search Tree from Sorted linked list
本文介绍了从排序链表创建平衡二叉搜索树的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
从排序的单向链表创建平衡二叉搜索树的最佳方法是什么?
What's the best way to create a balanced binary search tree from a sorted singly linked list?
推荐答案
如何自下而上创建节点?
How about creating nodes bottom-up?
这个解决方案的时间复杂度是 O(N).我的博文中有详细解释:
This solution's time complexity is O(N). Detailed explanation in my blog post:
http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html
我们只需要两次遍历链表.先遍历得到链表的长度(然后作为参数n传入函数),然后按照链表的顺序创建节点.
Two traversal of the linked list is all we need. First traversal to get the length of the list (which is then passed in as the parameter n into the function), then create nodes by the list's order.
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);
}
这篇关于从排序链表创建平衡二叉搜索树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文