Convert Sorted List to Binary Search Tree leetcode java

题目：

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

题解：

之前做过一道是从sorted array转换到BinarySearchTree的，方法还是一样二分法。但是构造树的方法不是由顶至下了，是要由低至上的建立。

代码如下：

 1     static ListNode h;

 2  

 3     public TreeNode sortedListToBST(ListNode head) {

 4         if (head == null)

 5             return null;

 6             

 7         h = head;

 8         

 9         int len = 0;

         ListNode temp = head;

         while(temp != null){

             len++;

             temp = temp.next;

         }   

         return sortedListToBST(0, len - 1);

     }

  

     public TreeNode sortedListToBST(int start, int end) {

         if (start > end)

             return null;

         int mid = (start + end) / 2;

         TreeNode left = sortedListToBST(start, mid - 1);

         TreeNode root = new TreeNode(h.val);

         root.left = left;

         h = h.next;

         TreeNode right = sortedListToBST(mid + 1, end);

         root.right = right;

  

         return root;

     }

Reference： http://www.programcreek.com/2013/01/leetcode-convert-sorted-list-to-binary-search-tree-java/

巴特西

Convert Sorted List to Binary Search Tree leetcode java

最新文章

热门文章