首页 > 其他 > 详细

Convert Sorted List to Binary Search Tree

时间:2014-02-06 16:35:18      阅读:328      评论:0      收藏:0      [点我收藏+]

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

bubuko.com,布布扣
 1  //              We shuould use a static variable int the recursive function!!!!
 2 public class Solution {
 3     static ListNode h;
 4     public TreeNode sortedListToBST(ListNode head) {
 5         if(head==null) return null;
 6         h = head;
 7         ListNode p =head;
 8         int len = 0;
 9         while(p!=null){
10             len++;
11             p=p.next;
12         }
13         
14         return get(0,len-1);
15     }
16     public TreeNode get(int start,int end){
17         if(start>end) return null;
18        int mid=start+(end-start)/2;
19        TreeNode left = get(start, mid-1);
20        TreeNode parent = new TreeNode(h.val);
21        parent.left = left;
22        h = h.next;
23        parent.right= get(mid+1,end);
24        return parent;
25     }
26 }
View Code

Convert Sorted List to Binary Search Tree

原文:http://www.cnblogs.com/krunning/p/3538791.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!