forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsortedListToBST.java
More file actions
106 lines (85 loc) · 2.55 KB
/
sortedListToBST.java
File metadata and controls
106 lines (85 loc) · 2.55 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package Algorithms.tree;
import Algorithms.algorithm.others.ListNode;
/**
* Definition for singly-linked list.
* public class ListNode {h
* 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 sortedListToBST {
public TreeNode sortedListToBST1(ListNode head) {
ListNode fast = head;
ListNode slow = head;
ListNode pre = head;
if (head == null) {
return null;
}
TreeNode root = null;
if (head.next == null) {
root = new TreeNode(head.val);
root.left = null;
root.right = null;
return root;
}
// get the middle node.
while (fast != null && fast.next != null) {
fast = fast.next.next;
// record the node before the SLOW.
pre = slow;
slow = slow.next;
}
// cut the list to two parts.
pre.next = null;
TreeNode left = sortedListToBST1(head);
TreeNode right = sortedListToBST1(slow.next);
root = new TreeNode(slow.val);
root.left = left;
root.right = right;
return root;
}
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
int size = 0;
ListNode cur = head;
while (cur != null) {
size++;
cur = cur.next;
}
CurrNode curNode = new CurrNode(head);
return sortedListToBSTHelp(curNode, size);
}
public class CurrNode {
ListNode node;
CurrNode(ListNode node) {
this.node = node;
}
}
// when the recursion is done, the curr node should point to the node
// which is the next of the block.
public TreeNode sortedListToBSTHelp(CurrNode curr, int size) {
if (size <= 0) {
return null;
}
TreeNode left = sortedListToBSTHelp(curr, size/2);
// because we want to deal with the right block.
TreeNode root = new TreeNode(curr.node.val);
curr.node = curr.node.next;
TreeNode right = sortedListToBSTHelp(curr, size - 1 - size/2);
root.left = left;
root.right = right;
return root;
}
}