446. Maximum Binary Tree
You are given an integer array nums whose values are all distinct. It defines a maximum binary tree, built like this:
- The root holds the largest value in the array.
- The left subtree is the maximum binary tree built from everything left of that largest value.
- The right subtree is the maximum binary tree built from everything right of it.
- An empty slice produces no node.
Your function receives nums and returns the root TreeNode of the maximum binary tree it defines. The construction is deterministic — distinct values mean there is exactly one such tree.
Example 1:
Input: nums = [3, 2, 1, 6, 0, 5]
Output: [6, 3, 5, null, 2, 0, null, null, 1]
Explanation: 6 is the overall maximum, so it is the root. [3, 2, 1] builds the left subtree (3 on top, then 2, then 1 hanging right-right), and [0, 5] builds the right subtree (5 on top with 0 as its left child).
Example 2:
Input: nums = [3, 2, 1]
Output: [3, null, 2, null, 1]
Explanation: Each maximum sits at the front of its slice, so every node has only a right child — the tree degenerates into a right-leaning chain.
Constraints:
- 1 ≤ nums.length ≤ 1000
- 0 ≤ nums[i] ≤ 1000
- All values of nums are distinct.
Hints:
The definition is already an algorithm: locate the maximum of the current slice, make it a node, recurse on the left and right slices. What is the total cost when the array is already sorted, and why?
For one pass: sweep left to right keeping a stack of nodes whose values decrease from bottom to top — that stack is exactly the right spine of the tree built so far. Each new value pops every smaller node (the last one popped becomes the new node's left child), and if a larger node remains on the stack, the new node attaches as its right child. Every node is pushed and popped at most once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 2, 1, 6, 0, 5]
Expected output: [6, 3, 5, null, 2, 0, null, null, 1]