Maximum Binary Tree
Problem Description
Question
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]
Example 2:
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000- All integers in
numsare unique.
Solve it on LeetCode
Approaches
1. Recursive Divide and Conquer
Intuition:
The problem requires constructing a binary tree where the root is the maximum number in the list, the left subtree is constructed from the elements before this maximum number, and the right subtree is from the elements after this maximum number. This naturally suggests a recursive approach where at each step, we select the maximum element as the root and recursively construct the left and right subtrees from the remaining elements.
Steps:
- Base Case: If the input list is empty, return
nullsince there's no tree to be constructed. - Find Maximum: Locate the maximum value in the array and identify its index.
- Construct Node: Create a tree node with the maximum value.
- Recursive Construction:
- Recursively construct the left subtree using the elements to the left of the maximum value.
- Recursively construct the right subtree using elements to the right.
- Link Subtrees: Assign the resulting subtrees to the left and right of the current node.
Code:
Complexity Analysis
- Time Complexity: O(n^2) in the worst case where the array is sorted and each recursive call will scan through the array slice to find the max. However, in average cases, this is closer to O(n log n).
- Space Complexity: O(n) to keep the recursion stack due to the depth of the recursion.