FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/problems/src/tree/MaximumBinaryTree.java at master · KindleBooks66/leetcode · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
KindleBooks66
/
leetcode
Public
forked from
gouthampradhan/leetcode
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
problems
/
src
/
tree
/
MaximumBinaryTree.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
74 lines (63 loc) · 1.96 KB
Breadcrumbs
leetcode
/
problems
/
src
/
tree
/
MaximumBinaryTree.java
Copy path
File metadata and controls
74 lines (63 loc) · 1.96 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
package
tree
;
/**
* Created by gouthamvidyapradhan on 19/08/2017. Given an integer array with no duplicates. A
* maximum tree building on this array is defined as follow:
*
* <p>The root is the maximum number in the array. The left subtree is the maximum tree constructed
* from left part subarray divided by the maximum number. The right subtree is the maximum tree
* constructed from right part subarray divided by the maximum number. Construct the maximum tree by
* the given array and output the root node of this tree.
*
* <p>Example 1: Input: [3,2,1,6,0,5] Output: return the tree root node representing the following
* tree:
*
* <p>6 / \ 3 5 \ / 2 0 \ 1
*
* <p>Note: The size of the given array will be in the range [1,1000].
*/
public
class
MaximumBinaryTree
{
public
static
class
TreeNode
{
int
val
;
TreeNode
left
;
TreeNode
right
;
TreeNode
(
int
x
) {
val
=
x
;
}
}
private
int
[][]
max
;
/**
* Main method
*
* @param args
* @throws Exception
*/
public
static
void
main
(
String
[]
args
)
throws
Exception
{
int
[]
nums
= {
3
,
2
,
1
,
6
,
0
,
5
};
TreeNode
root
=
new
MaximumBinaryTree
().
constructMaximumBinaryTree
(
nums
);
System
.
out
.
println
(
root
.
val
);
// print root
}
public
TreeNode
constructMaximumBinaryTree
(
int
[]
nums
) {
max
=
new
int
[
nums
.
length
][
nums
.
length
];
// pre-fill with initial values
for
(
int
i
=
0
;
i
<
nums
.
length
;
i
++) {
max
[
i
][
i
] =
i
;
}
// pre-calculate max for range index
for
(
int
i
=
0
;
i
<
nums
.
length
;
i
++) {
for
(
int
j
=
i
+
1
;
j
<
nums
.
length
;
j
++) {
max
[
i
][
j
] =
nums
[
max
[
i
][
j
-
1
]] >
nums
[
j
] ?
max
[
i
][
j
-
1
] :
j
;
}
}
return
build
(
0
,
nums
.
length
-
1
,
nums
);
}
private
TreeNode
build
(
int
s
,
int
e
,
int
[]
nums
) {
if
(
s
<=
e
) {
int
val
=
nums
[
max
[
s
][
e
]];
TreeNode
n
=
new
TreeNode
(
val
);
n
.
left
=
build
(
s
,
max
[
s
][
e
] -
1
,
nums
);
n
.
right
=
build
(
max
[
s
][
e
] +
1
,
e
,
nums
);
return
n
;
}
return
null
;
}
}
Back
|
FazBrowse Home
|
New Git URL