forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBSTtoDLL.java
More file actions
140 lines (120 loc) · 3.83 KB
/
BSTtoDLL.java
File metadata and controls
140 lines (120 loc) · 3.83 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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
import java.util.ArrayList;
import java.util.Stack;
/**
* Convert a BST to a sorted circular doubly-linked list in-place. Think of the
* left and right pointers as synonymous to the previous and next pointers in a
* doubly-linked list.
* <p/>
* This is a modified in-order traversal adapted to this problem. prev (init to
* NULL) is used to keep track of previously traversed node. head pointer is
* updated with the list's head as recursion ends.
* <p/>
* do it in place. time complexity: O(n)
*/
public class BSTtoDLL {
public static void main(String[] args) {
Node root = new Node(10);
Node node5 = new Node(5);
Node node15 = new Node(15);
Node node6 = new Node(6);
Node node20 = new Node(20);
Node node3 = new Node(3);
Node node12 = new Node(12);
Node node14 = new Node(14);
root.insert(node5);
root.insert(node6);
root.insert(node15);
root.insert(node20);
root.insert(node3);
root.insert(node12);
root.insert(node14);
ArrayList<Node> dll = bstToDLL(root);
printDll(dll);
bstToDllinPlace(root);
printDll(head);
}
public static void printDll(Node n) {
if (n == null) {
System.out.println("null");
} else {
int s = n.value;
System.out.print(n.value + " ");
n = n.right;
while (n.value != s) {
System.out.print(n.value + " ");
n = n.right;
}
}
System.out.println();
}
public static void printDll(ArrayList<Node> dll) {
if (dll.size() != 0) {
for (Node n : dll) {
System.out.print(n.value + " ");
}
}
System.out.println();
}
// not in place
public static ArrayList<Node> bstToDLL(Node node) {
if (node == null)
return null;
Stack<Node> stack = new Stack<Node>();
ArrayList<Node> dll = new ArrayList<Node>();
Node current = node;
boolean done = false;
while (!done) {
if (current != null) {
stack.push(current);
current = current.left;
} else {
if (stack.isEmpty()) {
done = true;
} else {
current = stack.pop();
dll.add(current);
current = current.right;
}
}
}
return dll;
}
// in place approach
static Node prev, head;
public static void bstToDllinPlace(Node p) {
if (p == null)
return;
bstToDllinPlace(p.left);
p.left = prev;
// current node (smallest element) is head of
// the list if previous node is not available
if (prev == null) {
head = p;
} else {
prev.right = p;
}
System.out.print("parent: " + p.value + " prev: ");
nodeToString(prev);
System.out.print(" head: ");
nodeToString(head);
// as soon as the recursion ends, the head's left pointer
// points to the last node, and the last node's right pointer
// points to the head pointer.
Node rightNode = p.right;
head.left = p;
p.right = head;
prev = p;
bstToDllinPlace(rightNode);
System.out.print("parent: " + p.value + " prev: ");
nodeToString(prev);
System.out.print(" head: ");
nodeToString(head);
}
public static void nodeToString(Node n) {
if (n == null) {
System.out.println("null");
} else {
System.out.println(n.value);
}
}
}