【刷题日记】654. 最大二叉树

本次刷题日记的第 98 篇，力扣题为：654. 最大二叉树

一、题目描述：

每日一题，每天一刷，继续干巴爹，最大二叉树看看是需要如何处理

二、这道题考察了什么思想？你的思路是什么？

题目给出一个不重复的数组，要求我们将数组转成树，对于转成树有如下要求：

• 生成的这棵树，根节点要是最大的，且根节点所在数组索引位置的左边的元素，需要放到根节点的左侧，根节点索引位置右边的数字要放到根节点的右侧
• 同理，对于根节点的左子树和右子树，他们选择自己根节点的时候，也是要用上述的规则，最终返回一棵满足要求的树

分析

看到二叉树的题，相对来说比较好解，或许在某些题型中，使用传统的递归或者层序遍历的方式来解决的话，时间复杂度会相对较高一些，不过咱们至少先要将题做出来，再去思考如何优化，则本次我们先分享前者

看到本题中给出示例数组

我们先来简单的找根节点，实际上按照题目要求，咱们直接遍历数组，找到数组中最大的一个数字，就是当前的根节点了，自然左子树和右子树，我们也就明确了

同理，我们来看左子树 的处理方式

其实这个时候，我们就已经发现，对于左子树去找根节点，咱们找的方式和最开始找整棵树的根节点的做法完全一样

那么这个时候，实际上我们就能很容易想到可以使用递归的方式来进行处理，递归中，需要变动的是递归函数参数中对应的实际数组

再来看到题目给出的基本代码，我们直接就将 constructMaximumBinaryTree 函数作为递归函数，每一次递归的时候咱们就去改变入参的数组即可

递归函数的逻辑是这样的：

1. 校验入参的传入的数组长度为 0 ，则直接返回为空地址（这也是递归函数的出口）
2. 遍历传入的数组，找到最大值和其对应的 nums 中的索引
3. 将最大值索引的左侧进行进一步递归，同理最大值索引右侧的元素进一步递归
4. 最终返回根节点即可

那么，看到这里，剩下的就来手撸代码吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 咱们直接使用递归的方式，找一棵树的根节点的方式和找子树根节点的方式，完全一样

编码如下：

/**
 * 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. 最大二叉树

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~