Medium

题目描述

给定一个不含重复元素的整数数组 nums。一个以此数组构建的最大二叉树定义如下：

  1. 二叉树的根是数组 nums 中的最大元素。
  2. 左子树是通过数组中最大值左边部分递归构造出的最大二叉树。
  3. 右子树是通过数组中最大值右边部分递归构造出的最大二叉树。

返回有给定数组构建的最大二叉树。

示例 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 中的所有整数互不相同

解题思路

这道题有两种主要解法：递归分治法和单调栈法。

递归分治法（推荐）： 根据题目描述，我们需要找到数组中的最大值作为根节点，然后将数组分为左右两部分，分别递归构建左右子树。这是一个典型的分治问题。对于每个子数组，我们重复相同的过程：找最大值、分割、递归构建。当子数组为空时，返回空节点作为递归出口。

单调栈法： 我们可以用单调递减栈来优化构建过程。从左到右遍历数组，维护一个单调递减的栈。当遇到比栈顶元素大的数时，说明栈顶元素应该作为当前元素的左子树。这种方法的时间复杂度更优，为O(n)。

两种方法各有特点：递归法思路直观，容易理解和实现；单调栈法效率更高，但理解稍复杂。对于这道题的数据规模，递归法已经足够高效且更易于理解。

代码实现

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return build(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* build(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        
        // 找到最大值及其索引
        int maxVal = nums[left];
        int maxIdx = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIdx = i;
            }
        }
        
        // 创建根节点
        TreeNode* root = new TreeNode(maxVal);
        
        // 递归构建左右子树
        root->left = build(nums, left, maxIdx - 1);
        root->right = build(nums, maxIdx + 1, right);
        
        return root;
    }
};

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            
            # 找到最大值及其索引
            max_val = max(nums[left:right+1])
            max_idx = nums.index(max_val, left, right+1)
            
            # 创建根节点
            root = TreeNode(max_val)
            
            # 递归构建左右子树
            root.left = build(left, max_idx - 1)
            root.right = build(max_idx + 1, right)
            
            return root
        
        return build(0, len(nums) - 1)

public class Solution {
    public TreeNode ConstructMaximumBinaryTree(int[] nums) {
        return Build(nums, 0, nums.Length - 1);
    }
    
    private TreeNode Build(int[] nums, int left, int right) {
        if (left > right) return null;
        
        // 找到最大值及其索引
        int maxVal = nums[left];
        int maxIdx = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIdx = i;
            }
        }
        
        // 创建根节点
        TreeNode root = new TreeNode(maxVal);
        
        // 递归构建左右子树
        root.left = Build(nums, left, maxIdx - 1);
        root.right = Build(nums, maxIdx + 1, right);
        
        return root;
    }
}

var constructMaximumBinaryTree = function(nums) {
    function build(left, right) {
        if (left > right) return null;
        
        // 找到最大值及其索引
        let maxVal = nums[left];
        let maxIdx = left;
        for (let i = left + 1; i <= right; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIdx = i;
            }
        }
        
        // 创建根节点
        const root = new TreeNode(maxVal);
        
        // 递归构建左右子树
        root.left = build(left, maxIdx - 1);
        root.right = build(maxIdx + 1, right);
        
        return root;
    }
    
    return build(0, nums.length - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
递归分治法O(n²)O(n)
单调栈法O(n)O(n)

说明：

  • 递归分治法：最坏情况下每次只能减少一个元素（如严格递增或递减数组），需要O(n²)时间；空间复杂度主要来自递归调用栈
  • 单调栈法：每个元素最多入栈出栈一次，时间复杂度为O(n)；空间复杂度来自栈的存储

相关题目