What is the main pattern used in Maximum Binary Tree?

The problem follows a binary-tree traversal and state tracking pattern, recursively dividing the array based on the maximum element.

Can Maximum Binary Tree be built iteratively?

Yes, using a monotonic stack approach, which assigns left children when popping smaller elements, reducing redundant maximum searches.

What is the time complexity for simple recursive construction?

It is O(n^2) because each recursive call scans the subarray for the maximum element.

How do you handle empty subarrays in recursion?

Return null for empty subarrays to ensure the parent node has no child in that direction.

Are all elements in nums unique for this problem?

Yes, Maximum Binary Tree requires that all integers in nums are unique to define a clear maximum at each step.

#654

Medium

auto_awesome二分·树·traversal

LeetCode 题解工作台

最大二叉树

给定一个不重复的整数数组 nums 。最大二叉树可以用下面的算法从 nums 递归地构建: 创建一个根节点，其值为 nums 中的最大值。递归地在最大值左边的子数组前缀上构建左子树。递归地在最大值右边的子数组后缀上构建右子树。返回 nums 构建的最大二叉树。示例 1…

数组分治栈树单调栈

题目描述

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

lightbulb

解题思路

方法一：递归

先找到数组 $nums$ 的最大元素所在的位置 $i$ ，将 $nums[i]$ 作为根节点，然后递归左右两侧的子数组，构建左右子树。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ ，其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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)

speed

复杂度分析

指标	值
时间	complexity is O(n^2) for simple recursion due to repeated max searches, but O(n) with a monotonic stack. Space complexity is O(n) for recursion stack or explicit data structures.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect you to explain recursive subtree construction and element selection.
question_mark
They may probe for iterative alternatives using a stack to reduce repeated max searches.
question_mark
Clarification questions often focus on handling empty arrays or single-element subarrays.

warning

常见陷阱

外企场景

error
Not correctly partitioning the array, leading to misplaced children.
error
Repeatedly scanning for the maximum without optimization, causing O(n^2) time.
error
Ignoring edge cases like empty subarrays or single-element segments.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Construct a maximum binary tree from a linked list instead of an array.
arrow_right_alt
Build a minimum binary tree by selecting the smallest element as root at each step.
arrow_right_alt
Return the preorder or inorder traversal of the maximum binary tree without building it explicitly.

help

常见问题

外企场景

继续练习

#1008 前序遍历构造二叉搜索树 #889 根据前序和后序遍历构造二叉树 #108 将有序数组转换为二叉搜索树