【刷题日记】654. 最大二叉树
本次刷题日记的第 98 篇，力扣题为：654. 最大二叉树
一、题目描述：
每日一题，每天一刷，继续干巴爹，最大二叉树看看是需要如何处理
二、这道题考察了什么思想？你的思路是什么？
题目给出一个不重复的数组，要求我们将数组转成树，对于转成树有如下要求：
- 生成的这棵树，根节点要是最大的，且根节点所在数组索引位置的左边的元素，需要放到根节点的左侧，根节点索引位置右边的数字要放到根节点的右侧
- 同理，对于根节点的左子树和右子树，他们选择自己根节点的时候，也是要用上述的规则，最终返回一棵满足要求的树
分析
看到二叉树的题，相对来说比较好解，或许在某些题型中，使用传统的递归或者层序遍历的方式来解决的话，时间复杂度会相对较高一些，不过咱们至少先要将题做出来，再去思考如何优化，则本次我们先分享前者
看到本题中给出示例数组
| 原数组 | 3 | 2 | 1 | 6 | 0 | 5 |
|---|
我们先来简单的找根节点，实际上按照题目要求，咱们直接遍历数组，找到数组中最大的一个数字，就是当前的根节点了，自然左子树和右子树，我们也就明确了
同理，我们来看左子树 的处理方式
其实这个时候，我们就已经发现，对于左子树去找根节点，咱们找的方式和最开始找整棵树的根节点的做法完全一样
那么这个时候，实际上我们就能很容易想到可以使用递归的方式来进行处理，递归中，需要变动的是递归函数参数中对应的实际数组
再来看到题目给出的基本代码，我们直接就将 constructMaximumBinaryTree 函数作为递归函数，每一次递归的时候咱们就去改变入参的数组即可
递归函数的逻辑是这样的：
- 校验入参的传入的数组长度为 0 ，则直接返回为空地址（这也是递归函数的出口）
- 遍历传入的数组，找到最大值和其对应的 nums 中的索引
- 将最大值索引的左侧进行进一步递归，同理最大值索引右侧的元素进一步递归
- 最终返回根节点即可
那么，看到这里，剩下的就来手撸代码吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 咱们直接使用递归的方式，找一棵树的根节点的方式和找子树根节点的方式，完全一样
编码如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func constructMaximumBinaryTree(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
var maxIdx = 0
// 找到最大值的索引
for i:=1; i< len(nums); i++ {
if nums[i] > nums[maxIdx] {
maxIdx = i
}
}
return &TreeNode{ nums[maxIdx], constructMaximumBinaryTree(nums[:maxIdx]), constructMaximumBinaryTree(nums[maxIdx+1:]) }
}
四、总结：
本次咱们这种解法来实现这个题，时间复杂度相对有点高，但是对于初次做这种题的话，能做出来就行，如果是需要进阶，可以尝试使用单调栈的方式来进行处理
本题这种使用递归的方式处理，时间复杂度在极端情况下会达到 O(n^2) ，在那种题目给出的数组是严格递增或者是严格递减的情况的时候
空间复杂度极端情况下是 O(n) ，那就是咱们要递归 n 层
原题地址：654. 最大二叉树
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~