首页 > 代码库 > Leetcode:Convert Sorted List to Binary Search Tree

Leetcode:Convert Sorted List to Binary Search Tree

Description :

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

分析:这道题目简单版是把一个排序好的数组转成平衡的二叉树。那样就很简单了,分治法搞定! 可以立即想一下如何做。

但是链表没有了随机访问的方法,当然也可以像数组那样做:1.直接将链表转到数组中来做,需要额外的空间。2.不随机访问

了,需要相应元素时顺序找到该元素,需要额外的时间O(nlogn); 

则我们想顺序访问链表,就可以建成二叉树,那么就需要和前面自顶向下的方法不同,考虑自低向上 去建立bst.具体分析见链接

http://leetcode.com/2010/11/convert-sorted-list-to-balancedbinary.html 

 

 1 BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
 2   if (start > end) return NULL;
 3   // same as (start+end)/2, avoids overflow
 4   int mid = start + (end - start) / 2;
 5   BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
 6   BinaryTree *parent = new BinaryTree(list->data);
 7   parent->left = leftChild;
 8   list = list->next;
 9   parent->right = sortedListToBST(list, mid+1, end);
10   return parent;
11 }
12  
13 BinaryTree* sortedListToBST(ListNode *head, int n) {
14   return sortedListToBST(head, 0, n-1);
15 }

个人认为这个代码非常难懂,要通过在纸上操作,才能大概弄懂他想干嘛。。  start 和 end变量时指示目前我们在处理范围内的元素,特别注意ListNode* &这个

引用标记,特别重要,因为在函数内部会有list = list->next; 也就是说一个函数内链表当前元素向前移动了,则以后当前元素都是这个最新元素了。 其建立的大致过

程是:一直递归到建立了最左节点,然后返回建立其父节点,然后建立其右子树,然后最左最下的子树就建立好了,然后类似的往上开始继续建立,只到建立好为止。