654. Maximum Binary Tree
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 <= 1000
0 <= nums[i] <= 1000
- All integers in
nums
are unique.
Rust Solution
struct Solution;
use rustgym_util::*;
trait Postorder {
fn from_vec(start: usize, end: usize, nums: &[i32]) -> Self;
}
impl Postorder for TreeLink {
fn from_vec(start: usize, end: usize, nums: &[i32]) -> Self {
if start == end {
None
} else {
if start + 1 == end {
tree!(nums[start])
} else {
let mut max_i = start;
let mut max = nums[start];
for i in start + 1..end {
if nums[i] > max {
max = nums[i];
max_i = i;
}
}
tree!(
max,
Self::from_vec(start, max_i, nums),
Self::from_vec(max_i + 1, end, nums)
)
}
}
}
}
impl Solution {
fn construct_maximum_binary_tree(nums: Vec<i32>) -> TreeLink {
TreeLink::from_vec(0, nums.len(), &nums)
}
}
#[test]
fn test() {
let nums = vec![3, 2, 1, 6, 0, 5];
let res = tree!(
6,
tree!(3, None, tree!(2, None, tree!(1))),
tree!(5, tree!(0), None)
);
assert_eq!(Solution::construct_maximum_binary_tree(nums), res);
}
Having problems with this solution? Click here to submit an issue on github.