@@ -0,0 +1,2020 @@
+package leetcode101_110;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**Given a singly linked list where elements are sorted in ascending order,%0A convert it to a height balanced BST.%0A * Created by eugene on 16/1/28.%0A */%0Apublic class ConvertSortedListToBinarySearchTree %7B%0A%0A    //Definition for a binary tree node.%0A    public static class TreeNode %7B%0A        int val;%0A        TreeNode left;%0A        TreeNode right;%0A        TreeNode(int x) %7B val = x; %7D%0A    %7D%0A%0A    // Definition for singly-linked list.%0A    public static class ListNode %7B%0A        int val;%0A        ListNode next;%0A        ListNode(int x) %7B val = x; %7D%0A    %7D%0A%0A    //%E8%8E%B7%E5%8F%96%E9%93%BE%E8%A1%A8%E9%95%BF%E5%BA%A6%E5%90%8E,%E8%87%AA%E5%BA%95%E5%90%91%E4%B8%8A(%E4%B8%AD%E5%BA%8F%E9%A1%BA%E5%BA%8F)%E9%80%92%E5%BD%92%E5%BB%BA%E6%A0%91%0A    private ListNode node = null;%0A    public TreeNode sortedListToBST(ListNode head) %7B%0A        if (head==null) return null;%0A        node = head;%0A        int len = 0;%0A        while (node!=null)%7B%0A            len++;%0A            node = node.next;%0A        %7D%0A        node = head;%0A        return sortedListToBST(0, len-1);%0A    %7D%0A    private TreeNode sortedListToBST(int l, int r)%7B%0A        if (l%3Er) return null;%0A        int m = (l+r)/2;%0A        TreeNode left = sortedListToBST(l, m-1);%0A        TreeNode root = new TreeNode(node.val);%0A        node = node.next;%0A        TreeNode right = sortedListToBST(m+1, r);%0A        root.left = left;%0A        root.right = right;%0A        return root;%0A    %7D%0A%0A%0A    //%E5%85%88%E5%B0%86%E9%93%BE%E8%A1%A8%E8%BD%AC%E4%B8%BA%E6%95%B0%E7%BB%84,%E5%86%8D%E8%87%AA%E9%A1%B6%E5%90%91%E4%B8%8B(%E5%85%88%E6%A0%B9%E5%86%8D%E5%B7%A6%E5%8F%B3%E5%AD%90%E6%A0%91)%E9%80%92%E5%BD%92%E5%BB%BA%E6%A0%91%0A    public TreeNode sortedListToBST1(ListNode head) %7B%0A        if (head==null) return null;%0A        ListNode node = head;%0A        List%3CInteger%3E list = new ArrayList%3C%3E();%0A        while (node!=null)%7B%0A            list.add(node.val);%0A            node = node.next;%0A        %7D%0A        return sortedArrayToBST(list, 0, list.size()-1);%0A    %7D%0A    private TreeNode sortedArrayToBST(List%3CInteger%3E nums, int l, int r)%7B%0A        if (l%3Er) return null;%0A        int m = (l+r)/2;%0A        TreeNode root = new TreeNode(nums.get(m));%0A        root.left = sortedArrayToBST(nums, l, m-1);%0A        root.right = sortedArrayToBST(nums, m+1, r);%0A        return root;%0A    %7D%0A%0A%7D%0A

Convert Sorted List to Binary Search Tree