Maximum binary tree

Array Divide and Conquer Stack Tree Monotonic Stack Binary Tree

86.3% acceptance

Feb 20, 2026

5415

351

Given an integer array nums with no duplicates, build a maximum binary tree. The root is the max of nums. The left subtree is built from the left part of nums (before the max), and the right subtree from the right part.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn construct_maximum_binary_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
    fn build(nums: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
      if nums.is_empty() { return None; }
      let (max_idx, _) = nums.iter().enumerate().max_by_key(|&(_, v)| v).unwrap();
      let node = Rc::new(RefCell::new(TreeNode::new(nums[max_idx])));
      node.borrow_mut().left = build(&nums[..max_idx]);
      node.borrow_mut().right = build(&nums[max_idx + 1..]);
      Some(node)
    }
    build(&nums)
  }
}