首页 > 代码库 > Convert Sorted List to Binary Search Tree leetcode java
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;
10 ListNode temp = head;
11 while(temp != null){
12 len++;
13 temp = temp.next;
14 }
15 return sortedListToBST(0, len - 1);
16 }
17
18 public TreeNode sortedListToBST(int start, int end) {
19 if (start > end)
20 return null;
21 int mid = (start + end) / 2;
22 TreeNode left = sortedListToBST(start, mid - 1);
23 TreeNode root = new TreeNode(h.val);
24 root.left = left;
25 h = h.next;
26 TreeNode right = sortedListToBST(mid + 1, end);
27 root.right = right;
28
29 return root;
30 }
2
3 public TreeNode sortedListToBST(ListNode head) {
4 if (head == null)
5 return null;
6
7 h = head;
8
9 int len = 0;
10 ListNode temp = head;
11 while(temp != null){
12 len++;
13 temp = temp.next;
14 }
15 return sortedListToBST(0, len - 1);
16 }
17
18 public TreeNode sortedListToBST(int start, int end) {
19 if (start > end)
20 return null;
21 int mid = (start + end) / 2;
22 TreeNode left = sortedListToBST(start, mid - 1);
23 TreeNode root = new TreeNode(h.val);
24 root.left = left;
25 h = h.next;
26 TreeNode right = sortedListToBST(mid + 1, end);
27 root.right = right;
28
29 return root;
30 }
Reference： http://www.programcreek.com/2013/01/leetcode-convert-sorted-list-to-binary-search-tree-java/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。