Description#
You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:
- Create a root node whose value is the maximum value in
nums. - Recursively build the left subtree on the subarray prefix to the left of the maximum value.
- Recursively build the right subtree on the subarray suffix to the right of the maximum value.
Return the maximum binary tree built from nums.
Example 1:
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
- The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
- Empty array, so no child.
- The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
- Empty array, so no child.
- Only one element, so child is a node with value 1.
- The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
- Only one element, so child is a node with value 0.
- Empty array, so no child.
Example 2:
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000- All integers in
nums are unique.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(nums):
if not nums:
return None
val = max(nums)
i = nums.index(val)
root = TreeNode(val)
root.left = dfs(nums[:i])
root.right = dfs(nums[i + 1 :])
return root
return dfs(nums)
|
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
| /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int[] nums;
public TreeNode constructMaximumBinaryTree(int[] nums) {
this.nums = nums;
return dfs(0, nums.length - 1);
}
private TreeNode dfs(int l, int r) {
if (l > r) {
return null;
}
int i = l;
for (int j = l; j <= r; ++j) {
if (nums[i] < nums[j]) {
i = j;
}
}
TreeNode root = new TreeNode(nums[i]);
root.left = dfs(l, i - 1);
root.right = dfs(i + 1, r);
return root;
}
}
|
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
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return dfs(nums, 0, nums.size() - 1);
}
TreeNode* dfs(vector<int>& nums, int l, int r) {
if (l > r) return nullptr;
int i = l;
for (int j = l; j <= r; ++j) {
if (nums[i] < nums[j]) {
i = j;
}
}
TreeNode* root = new TreeNode(nums[i]);
root->left = dfs(nums, l, i - 1);
root->right = dfs(nums, i + 1, r);
return root;
}
};
|
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
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructMaximumBinaryTree(nums []int) *TreeNode {
var dfs func(l, r int) *TreeNode
dfs = func(l, r int) *TreeNode {
if l > r {
return nil
}
i := l
for j := l; j <= r; j++ {
if nums[i] < nums[j] {
i = j
}
}
root := &TreeNode{Val: nums[i]}
root.Left = dfs(l, i-1)
root.Right = dfs(i+1, r)
return root
}
return dfs(0, len(nums)-1)
}
|
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
| /**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function constructMaximumBinaryTree(nums: number[]): TreeNode | null {
const n = nums.length;
if (n === 0) {
return null;
}
const [val, i] = nums.reduce((r, v, i) => (r[0] < v ? [v, i] : r), [-1, 0]);
return new TreeNode(
val,
constructMaximumBinaryTree(nums.slice(0, i)),
constructMaximumBinaryTree(nums.slice(i + 1)),
);
}
|
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
| // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
fn construct(nums: &Vec<i32>, start: usize, end: usize) -> Option<Rc<RefCell<TreeNode>>> {
if start >= end {
return None;
}
let mut idx = 0;
let mut max_val = -1;
for i in start..end {
if nums[i] > max_val {
idx = i;
max_val = nums[i];
}
}
Some(
Rc::new(
RefCell::new(TreeNode {
val: max_val,
left: Self::construct(nums, start, idx),
right: Self::construct(nums, idx + 1, end),
})
)
)
}
pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
Self::construct(&nums, 0, nums.len())
}
}
|
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
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* construct(int* nums, int start, int end) {
if (start >= end) {
return NULL;
}
int idx = 0;
int maxVal = -1;
for (int i = start; i < end; i++) {
if (nums[i] > maxVal) {
idx = i;
maxVal = nums[i];
}
}
struct TreeNode* res = (struct TreeNode*) malloc(sizeof(struct TreeNode));
res->val = maxVal;
res->left = construct(nums, start, idx);
res->right = construct(nums, idx + 1, end);
return res;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
return construct(nums, 0, numsSize);
}
|
Solution 2#
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
| # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(l, r):
if l > r:
return None
val = tree.query(1, l, r)
root = TreeNode(val)
root.left = dfs(l, d[val] - 1)
root.right = dfs(d[val] + 1, r)
return root
d = {v: i for i, v in enumerate(nums, 1)}
tree = SegmentTree(nums)
return dfs(1, len(nums))
class Node:
def __init__(self):
self.l = 0
self.r = 0
self.v = 0
class SegmentTree:
def __init__(self, nums):
self.nums = nums
n = len(nums)
self.tr = [Node() for _ in range(n << 2)]
self.build(1, 1, n)
def build(self, u, l, r):
self.tr[u].l, self.tr[u].r = l, r
if l == r:
self.tr[u].v = self.nums[l - 1]
return
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
self.pushup(u)
def query(self, u, l, r):
if self.tr[u].l >= l and self.tr[u].r <= r:
return self.tr[u].v
mid = (self.tr[u].l + self.tr[u].r) >> 1
v = 0
if l <= mid:
v = max(v, self.query(u << 1, l, r))
if r > mid:
v = max(v, self.query(u << 1 | 1, l, r))
return v
def pushup(self, u):
self.tr[u].v = max(self.tr[u << 1].v, self.tr[u << 1 | 1].v)
|
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
| /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private SegmentTree tree;
private int[] nums;
private static int[] d = new int[1010];
public TreeNode constructMaximumBinaryTree(int[] nums) {
int n = nums.length;
this.nums = nums;
tree = new SegmentTree(nums);
for (int i = 0; i < n; ++i) {
d[nums[i]] = i + 1;
}
return dfs(1, n);
}
private TreeNode dfs(int l, int r) {
if (l > r) {
return null;
}
int val = tree.query(1, l, r);
TreeNode root = new TreeNode(val);
root.left = dfs(l, d[val] - 1);
root.right = dfs(d[val] + 1, r);
return root;
}
}
class Node {
int l;
int r;
int v;
}
class SegmentTree {
Node[] tr;
int[] nums;
public SegmentTree(int[] nums) {
int n = nums.length;
this.nums = nums;
tr = new Node[n << 2];
for (int i = 0; i < tr.length; ++i) {
tr[i] = new Node();
}
build(1, 1, n);
}
private void build(int u, int l, int r) {
tr[u].l = l;
tr[u].r = r;
if (l == r) {
tr[u].v = nums[l - 1];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
public int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].v;
}
int mid = (tr[u].l + tr[u].r) >> 1;
int v = 0;
if (l <= mid) {
v = query(u << 1, l, r);
}
if (r > mid) {
v = Math.max(v, query(u << 1 | 1, l, r));
}
return v;
}
private void pushup(int u) {
tr[u].v = Math.max(tr[u << 1].v, tr[u << 1 | 1].v);
}
}
|
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
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Node {
public:
int l, r, v;
};
class SegmentTree {
public:
vector<Node*> tr;
vector<int> nums;
SegmentTree(vector<int>& nums) {
this->nums = nums;
int n = nums.size();
tr.resize(n << 2);
for (int i = 0; i < tr.size(); ++i) tr[i] = new Node();
build(1, 1, n);
}
void build(int u, int l, int r) {
tr[u]->l = l;
tr[u]->r = r;
if (l == r) {
tr[u]->v = nums[l - 1];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
int query(int u, int l, int r) {
if (tr[u]->l >= l && tr[u]->r <= r) return tr[u]->v;
int mid = (tr[u]->l + tr[u]->r) >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
void pushup(int u) {
tr[u]->v = max(tr[u << 1]->v, tr[u << 1 | 1]->v);
}
};
class Solution {
public:
SegmentTree* tree;
vector<int> nums;
vector<int> d;
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
tree = new SegmentTree(nums);
this->nums = nums;
d.assign(1010, 0);
int n = nums.size();
for (int i = 0; i < n; ++i) d[nums[i]] = i + 1;
return dfs(1, nums.size());
}
TreeNode* dfs(int l, int r) {
if (l > r) {
return nullptr;
}
int val = tree->query(1, l, r);
TreeNode* root = new TreeNode(val);
root->left = dfs(l, d[val] - 1);
root->right = dfs(d[val] + 1, r);
return root;
}
};
|
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
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructMaximumBinaryTree(nums []int) *TreeNode {
d := make([]int, 1010)
for i, v := range nums {
d[v] = i + 1
}
tree := newSegmentTree(nums)
var dfs func(l, r int) *TreeNode
dfs = func(l, r int) *TreeNode {
if l > r {
return nil
}
val := tree.query(1, l, r)
root := &TreeNode{Val: val}
root.Left = dfs(l, d[val]-1)
root.Right = dfs(d[val]+1, r)
return root
}
return dfs(1, len(nums))
}
type node struct {
l int
r int
v int
}
type segmentTree struct {
nums []int
tr []*node
}
func newSegmentTree(nums []int) *segmentTree {
n := len(nums)
tr := make([]*node, n<<2)
for i := range tr {
tr[i] = &node{}
}
t := &segmentTree{nums, tr}
t.build(1, 1, n)
return t
}
func (t *segmentTree) build(u, l, r int) {
t.tr[u].l, t.tr[u].r = l, r
if l == r {
t.tr[u].v = t.nums[l-1]
return
}
mid := (l + r) >> 1
t.build(u<<1, l, mid)
t.build(u<<1|1, mid+1, r)
t.pushup(u)
}
func (t *segmentTree) query(u, l, r int) int {
if t.tr[u].l >= l && t.tr[u].r <= r {
return t.tr[u].v
}
mid := (t.tr[u].l + t.tr[u].r) >> 1
v := 0
if l <= mid {
v = t.query(u<<1, l, r)
}
if r > mid {
v = max(v, t.query(u<<1|1, l, r))
}
return v
}
func (t *segmentTree) pushup(u int) {
t.tr[u].v = max(t.tr[u<<1].v, t.tr[u<<1|1].v)
}
|
Solution 3#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
stk = []
for v in nums:
node = TreeNode(v)
last = None
while stk and stk[-1].val < v:
last = stk.pop()
node.left = last
if stk:
stk[-1].right = node
stk.append(node)
return stk[0]
|
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
| /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
Deque<TreeNode> stk = new ArrayDeque<>();
for (int v : nums) {
TreeNode node = new TreeNode(v);
TreeNode last = null;
while (!stk.isEmpty() && stk.peek().val < v) {
last = stk.pop();
}
node.left = last;
if (!stk.isEmpty()) {
stk.peek().right = node;
}
stk.push(node);
}
return stk.getLast();
}
}
|
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
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
stack<TreeNode*> stk;
for (int v : nums) {
TreeNode* node = new TreeNode(v);
TreeNode* last = nullptr;
while (!stk.empty() && stk.top()->val < v) {
last = stk.top();
stk.pop();
}
node->left = last;
if (!stk.empty()) {
stk.top()->right = node;
}
stk.push(node);
}
while (stk.size() > 1) {
stk.pop();
}
return stk.top();
}
};
|
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
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructMaximumBinaryTree(nums []int) *TreeNode {
stk := []*TreeNode{}
for _, v := range nums {
node := &TreeNode{Val: v}
var last *TreeNode
for len(stk) > 0 && stk[len(stk)-1].Val < v {
last = stk[len(stk)-1]
stk = stk[:len(stk)-1]
}
node.Left = last
if len(stk) > 0 {
stk[len(stk)-1].Right = node
}
stk = append(stk, node)
}
return stk[0]
}
|
