forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathConvertSortedListtoBinarySearchTree.java
More file actions
executable file
·89 lines (88 loc) · 2.63 KB
/
ConvertSortedListtoBinarySearchTree.java
File metadata and controls
executable file
·89 lines (88 loc) · 2.63 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
Author: King, wangjingui@outlook.com
Date: Dec 12, 2014
Problem: Convert Sorted List to Binary Search Tree
Difficulty: Medium
Source: https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
Notes:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution: 1. Recursion. In-order. O(n)
2. Recursion . Pre-order.
3. pre-order.
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode iter;
public TreeNode sortedListToBST_1(ListNode head) {
iter = head;
int len = 0;
while (head != null) {
++len;
head = head.next;
}
return sortedListToBSTRe1(len);
}
public TreeNode sortedListToBSTRe1(int len) {
if (len == 0) return null;
int mid = len / 2;
TreeNode left = sortedListToBSTRe1(mid);
TreeNode root = new TreeNode(iter.val);
root.left = left;
iter = iter.next;
root.right = sortedListToBSTRe1(len - 1 - mid);
return root;
}
public TreeNode sortedListToBST_2(ListNode head) {
return sortedListToBSTRe2(head, null);
}
public TreeNode sortedListToBSTRe2(ListNode start, ListNode end) {
if(start == end) return null;
ListNode pre = null;
ListNode slow = start;
ListNode fast = start;
while (fast!=end&&fast.next!=end) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode node = new TreeNode(slow.val);
node.left = sortedListToBSTRe2(start, slow);
node.right = sortedListToBSTRe2(slow.next,end);
return node;
}
public TreeNode sortedListToBST_3(ListNode head) {
if (head == null) return null;
if (head.next==null) return new TreeNode(head.val);
ListNode slow = head;
ListNode fast = head;
ListNode pre = null;
while(fast.next!=null && fast.next.next!=null) {
pre = slow;
slow = slow.next;
fast =fast.next.next;
}
fast = slow.next;
TreeNode node = new TreeNode(slow.val);
if(pre!=null) {
pre.next = null;
node.left = sortedListToBST_3(head);
}
node.right = sortedListToBST_3(fast);
return node;
}
}