最大二叉树

标签: 栈 树 数组 分治 二叉树 单调栈

难度: Medium

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

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

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

Submission

运行时间: 168 ms

内存: 15.3 MB

# 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]) -> TreeNode:
        def helper(lo, hi):
            if lo > hi:
                return
            max_value = nums[hi]
            index = hi
            for i in range(lo, hi):
                if nums[i] > max_value:
                    max_value = nums[i]
                    index = i

            root = TreeNode(max_value)
            root.left = helper(lo, index-1)
            root.right = helper(index+1, hi)
            return root

        return helper(0, len(nums)-1)

Explain

这个题解采用递归的方式来构建最大二叉树。首先找到数组中的最大值及其下标，将最大值作为根节点。然后递归地在最大值左边的子数组构建左子树，在最大值右边的子数组构建右子树。通过递归地把数组分割成更小的子数组，直到子数组为空时返回 null，最终完成整棵最大二叉树的构建。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        def helper(lo, hi):
            if lo > hi:
                return
            # 找到数组中的最大值及其下标
            max_value = nums[hi]
            index = hi
            for i in range(lo, hi):
                if nums[i] > max_value:
                    max_value = nums[i]
                    index = i

            # 将最大值作为根节点
            root = TreeNode(max_value)
            # 递归构建左子树
            root.left = helper(lo, index-1)
            # 递归构建右子树 
            root.right = helper(index+1, hi)
            return root

        return helper(0, len(nums)-1)

Explore

在递归函数中，通过传递子数组的起始索引（lo）和结束索引（hi）来处理边界。每次递归调用前，检查lo是否大于hi，如果是，则返回null，表示当前子数组为空，不需要创建节点。这样的检查确保了每次递归都严格在定义的子数组范围内操作，避免了数组越界的问题。

最大二叉树的定义是根节点必须是子数组中的最大值，左子树和右子树分别构建于根节点的最大值的左侧和右侧子数组。因此，一旦确定了子数组中的最大值，该值自然成为当前子树的根节点。其他元素的相对位置会在递归调用中进一步处理，它们将构成根节点的左子树或右子树，依据它们在原数组中的位置。

在单次递归中，使用线性搜索是必须的，因为我们需要在不同的子数组中重复查找最大值。尽管如此，整体性能可以通过其他数据结构如分段树或二叉索引树来优化，这些结构能在对数时间内找到子数组的最大值。但这会增加实现的复杂性，并且仅在重复询问子数组最大值的场景中才显得更优。在单次构建最大二叉树的情况下，这种优化的必要性较小。

如果输入数组是升序或降序排序的，构建的最大二叉树将形成一个斜树（所有节点只有左子节点或只有右子节点）。这种情况下，递归的深度等于数组的长度，因此性能将降低到最差，即O(n^2)复杂度，因为每次递归都必须遍历剩余的全部元素来找到最大值。这种情况下，性能显著下降，因为树的高度最大化，递归调用次数和每次调用处理的数组长度都最大。