LeetCode 654. 最大二叉树

654. 最大二叉树

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

链接 https://leetcode.cn/problems/maximum-binary-tree/

其他思路

1. 递归
   （1）最简单的方法是直接按照题目描述进行模拟。
   （2）我们用递归函数construct(nums,left,right) 表示对数组 nums 中从nums[left] 到 nums[right] 的元素构建一棵树。我们首先找到这一区间中的最大值，记为 nums 中从 nums[best]，这样就确定了根节点的值。随后我们就可以进行递归：左子树为 construct(nums,left,best−1)；右子树为construct(nums,best+1,right)。
   （3）当递归到一个无效的区间（即 left>right）时，便可以返回一棵空的树。

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def construct(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            
            best = left
            for i in range(left + 1, right + 1):
                if nums[i] > nums[best
1
2
3
4
5
6
7
8