FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
algorithm/PuzzleCoding/src/LargestBSTSubtree.java at master · wodgithub/algorithm · GitHub
wodgithub
algorithm
Repository navigation
Code
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
LargestBSTSubtree.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
184 lines (158 loc) · 6.73 KB
Breadcrumbs
algorithm
/
PuzzleCoding
/
src
/
LargestBSTSubtree.java
Copy path
File metadata and controls
184 lines (158 loc) · 6.73 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
/**
* Given a binary tree,
* find the largest subtree which is a Binary Search Tree (BST),
* where largest means subtree with largest number of nodes in it.
*/
public
class
LargestBSTSubtree
{
public
static
class
LargestBST
{
public
Node
node
;
public
int
maxNode
;
public
int
min
;
public
int
max
;
public
LargestBST
(
Node
n
,
int
number
,
int
min_value
,
int
max_value
) {
node
=
n
;
max
=
max_value
;
min
=
min_value
;
maxNode
=
number
;
}
}
// end of class LargestBST
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
node7
=
new
Node
(
7
);
node15
.
right
=
node7
;
Node
node3
=
new
Node
(
3
);
Node
node12
=
new
Node
(
12
);
Node
node11
=
new
Node
(
11
);
Node
node13
=
new
Node
(
13
);
Node
node14
=
new
Node
(
14
);
root
.
insert
(
node5
);
root
.
insert
(
node6
);
root
.
insert
(
node15
);
root
.
insert
(
node3
);
root
.
insert
(
node12
);
root
.
insert
(
node11
);
root
.
insert
(
node13
);
root
.
insert
(
node14
);
int
result
=
largestBSTSubtree
(
root
);
System
.
out
.
println
(
"largest bst (may not include all children): "
+
result
);
LargestBST
largeBST
=
largestBSTSubtree1
(
root
);
if
(
largeBST
!=
null
)
System
.
out
.
println
(
largeBST
.
node
.
value
+
" : size "
+
largeBST
.
maxNode
);
LargestBST
largeBST2
=
largestBSTSubtree2
(
root
);
if
(
largeBST2
!=
null
)
System
.
out
.
println
(
largeBST2
.
node
.
value
+
" : size "
+
largeBST2
.
maxNode
);
}
// Given a binary tree, find the largest Binary Search Tree (BST),
// where largest means BST with largest number of nodes in it.
// The largest BST may or may not include all of its descendants.
public
static
int
largestBSTSubtree
(
Node
node
) {
if
(
node
==
null
)
return
0
;
if
(
node
.
left
==
null
&&
node
.
right
==
null
)
return
1
;
int
leftNode
=
largestBSTSubtree
(
node
.
left
);
int
rightNode
=
largestBSTSubtree
(
node
.
right
);
if
(
node
.
left
!=
null
&&
node
.
right
!=
null
) {
if
((
node
.
left
.
value
<
node
.
value
) && (
node
.
right
.
value
>
node
.
value
)) {
return
leftNode
+
rightNode
+
1
;
}
else
if
(
node
.
left
.
value
<
node
.
value
) {
return
leftNode
+
1
;
}
else
if
(
node
.
right
.
value
>
node
.
value
) {
return
rightNode
+
1
;
}
else
{
return
Math
.
max
(
rightNode
,
leftNode
);
}
}
else
if
(
node
.
left
!=
null
) {
if
(
node
.
left
.
value
<
node
.
value
)
return
leftNode
+
1
;
else
return
leftNode
;
}
else
{
// if (node.right != null){
if
(
node
.
value
<
node
.
right
.
value
)
return
rightNode
+
1
;
else
return
rightNode
;
}
}
// Given a binary tree, find the largest Binary Search Tree (BST),
// where largest means BST with largest number of nodes in it.
// The largest BST may or may not include all of its descendants.
public
static
LargestBST
largestBSTSubtree1
(
Node
node
) {
if
(
node
==
null
)
return
null
;
if
(
node
.
left
==
null
&&
node
.
right
==
null
) {
return
new
LargestBST
(
node
,
node
.
size
(),
node
.
value
,
node
.
value
);
}
LargestBST
leftNode
=
largestBSTSubtree1
(
node
.
left
);
LargestBST
rightNode
=
largestBSTSubtree1
(
node
.
right
);
if
(
leftNode
!=
null
&&
rightNode
!=
null
) {
if
((
node
.
value
>
leftNode
.
max
&&
node
.
left
==
leftNode
.
node
)
&& (
node
.
value
<
rightNode
.
min
&&
node
.
right
==
rightNode
.
node
)) {
LargestBST
bst
=
new
LargestBST
(
node
,
leftNode
.
maxNode
+
rightNode
.
maxNode
+
1
,
leftNode
.
min
,
rightNode
.
max
);
return
bst
;
}
else
if
(
node
.
value
>
leftNode
.
max
&&
node
.
left
==
leftNode
.
node
) {
return
new
LargestBST
(
node
,
leftNode
.
maxNode
+
1
,
leftNode
.
min
,
node
.
value
);
}
else
if
(
node
.
value
<
rightNode
.
min
&&
node
.
right
==
rightNode
.
node
) {
return
new
LargestBST
(
node
,
rightNode
.
maxNode
+
1
,
node
.
value
,
rightNode
.
max
);
}
else
{
return
(
leftNode
.
maxNode
>
rightNode
.
maxNode
) ?
leftNode
:
rightNode
;
}
}
else
if
(
leftNode
!=
null
) {
if
(
node
.
value
>
leftNode
.
max
&&
node
.
left
==
leftNode
.
node
) {
return
new
LargestBST
(
node
,
leftNode
.
maxNode
+
1
,
leftNode
.
min
,
node
.
value
);
}
else
{
return
leftNode
;
}
}
else
if
(
rightNode
!=
null
) {
if
(
node
.
value
<
rightNode
.
min
&&
node
.
right
==
rightNode
.
node
) {
return
new
LargestBST
(
node
,
rightNode
.
maxNode
+
1
,
node
.
value
,
rightNode
.
max
);
}
else
{
return
rightNode
;
}
}
return
null
;
}
// Given a binary tree, find the largest Binary Search Tree (BST),
// where largest means BST with largest number of nodes in it.
// The largest BST must include all of its descendants.
public
static
LargestBST
largestBSTSubtree2
(
Node
node
) {
if
(
node
==
null
)
return
null
;
if
(
node
.
left
==
null
&&
node
.
right
==
null
) {
return
new
LargestBST
(
node
,
node
.
size
(),
node
.
value
,
node
.
value
);
}
LargestBST
leftNode
=
largestBSTSubtree2
(
node
.
left
);
LargestBST
rightNode
=
largestBSTSubtree2
(
node
.
right
);
if
(
leftNode
!=
null
&&
rightNode
!=
null
) {
if
((
node
.
value
>
leftNode
.
max
&&
node
.
left
==
leftNode
.
node
)
&& (
node
.
value
<
rightNode
.
min
&&
node
.
right
==
rightNode
.
node
)) {
LargestBST
bst
=
new
LargestBST
(
node
,
leftNode
.
maxNode
+
rightNode
.
maxNode
+
1
,
leftNode
.
min
,
rightNode
.
max
);
return
bst
;
}
else
{
return
(
leftNode
.
maxNode
>
rightNode
.
maxNode
) ?
leftNode
:
rightNode
;
}
}
else
if
(
leftNode
!=
null
) {
if
(
node
.
value
>
leftNode
.
max
&&
node
.
left
==
leftNode
.
node
) {
return
new
LargestBST
(
node
,
leftNode
.
maxNode
+
1
,
leftNode
.
min
,
node
.
value
);
}
else
{
return
leftNode
;
}
}
else
if
(
rightNode
!=
null
) {
if
(
node
.
value
<
rightNode
.
min
&&
node
.
right
==
rightNode
.
node
) {
return
new
LargestBST
(
node
,
rightNode
.
maxNode
+
1
,
node
.
value
,
rightNode
.
max
);
}
else
{
return
rightNode
;
}
}
return
null
;
}
}
Back
|
FazBrowse Home
|
New Git URL