每日一题2022.8.20——最大二叉树

2024年04月23日

luoyang

9 评论

leetcode

暂无标签

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

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

### 输入输出
#### 示例1
[![](https://assets.leetcode.com/uploads/2020/12/24/tree1.jpg)](https://assets.leetcode.com/uploads/2020/12/24/tree1.jpg)
```python
输入：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 的节点。
        - 空数组，无子节点。

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

### 题目解答
很明显，这个是一个递归问题。
我们选择数组中最大的元素之后，又将整个数组分成2部分，依然对这2部分分别找最大值，直到数组为空。
```python
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        def buildT(nums, left, right):
            if left > right:
                return None
            max_num = nums[left]
            max_index = left
            for i in range(left, right + 1):
                if nums[i] > max_num:
                    max_num = nums[i]
                    max_index = i
            root = TreeNode(max_num)
            root.left = buildT(nums, left, max_index-1)
            root.right = buildT(nums, max_index + 1, right)
            return root
        return buildT(nums, 0, len(nums)-1)
```

最后编辑：2024年04月23日 ©著作权归作者所有

已有 9 条评论

znsvyppprs 2024年09月23日 02:14
回复

叼茂SEO.bfbikes.com
vdcxubrldb 2024年09月23日 09:14
回复

看的我热血沸腾啊https://www.jiwenlaw.com/
uojdddvker 2024年10月19日 14:44
回复

哈哈哈，写的太好了https://www.cscnn.com/
hllfaobkke 2024年10月19日 14:44
回复

文章的确不错啊https://www.cscnn.com/
nweoakpvbu 2024年12月15日 07:23
回复

《血光假期》恐怖片高清在线免费观看：https://www.jgz518.com/xingkong/44272.html
zfuieiwdjr 2025年02月28日 18:36
回复

?技术类评语?
http://www.baidu.com 2025年10月12日 21:04
回复

hello
鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099 2025年11月02日 13:56
回复

华纳东方明珠客服电话是多少？（▲18288362750?《?微信STS5099? 】
如何联系华纳东方明珠客服？（▲18288362750?《?微信STS5099? 】
华纳东方明珠官方客服联系方式？（▲18288362750?《?微信STS5099?
华纳东方明珠客服热线？（▲18288362750?《?微信STS5099?
华纳东方明珠24小时客服电话？（▲18288362750?《?微信STS5099? 】
华纳东方明珠官方客服在线咨询？（▲18288362750?《?微信STS5099?
鍗庣撼鍏徃鍚堜綔寮€鎴锋墍闇€鏉愭枡锛熺數璇濆彿鐮?5587291507 寰俊STS5099 2025年11月17日 14:40
回复

华纳圣淘沙开户步骤详解（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司开户流程全解析（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司账户注册指南（183-8890-9465—?薇-STS5099【6011643】
新手如何开通华纳圣淘沙公司账户（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙企业开户标准流程（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司开户：从零到一（183-8890-9465—?薇-STS5099【6011643】
官方指南：华纳圣淘沙公司开户流程（183-8890-9465—?薇-STS5099【6011643】
华纳圣淘沙公司开户流程说明书（183-8890-9465—?薇-STS5099【6011643】