专栏首页码上积木LeetCode题解—最大二叉树

LeetCode题解—最大二叉树

前言

上一期我们总结了二叉树的递归遍历方法,其实二叉树的很多题目都涉及到了递归。

因为递归的思想,用同样的逻辑去完成不同节点的构建就很符合二叉树的数据结构,今天我们就来看另一道与递归有关的二叉树题,希望能让你加深印象。

题目:最大二叉树

给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下:

二叉树的根是数组 nums 中的最大元素。左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。返回有给定数组 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] 。
    • 只有一个元素,所以子节点是一个值为 0 的节点。
    • 空数组,无子节点。
    • 空数组,无子节点。
    • [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
    • 空数组,无子节点。
    • 只有一个元素,所以子节点是一个值为 1 的节点。
    • [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
    • [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。

分析

题意还是比较简单的,示例中也具体说明了。

就是找到数组中最大的数字作为根节点,然后将最大数字两边的数组继续构建成左右子树即可,所以我们可以按照题意写一段伪代码:

Tree buildTreebyFindMax(int[] nums , int leftIndex, int rightIndex){
    //找到最大值的下标
    int maxIndex = findMax(nums);
    //构建根节点为最大值的树
    TreeNode root = new TreeNode(nums[maxIndex]);
    //递归获取左子树
    root.left = buildTreebyFindMax(nums,leftIndex, maxNum);
    //递归获取右子树
    root.right = buildTreebyFindMax(nums, maxNum+1, rightIndex);

    return root;
}

只要给定每次递归中的左限定节点后右限定节点,就可以找到这个限定范围内 数组的最大值,然后作为一个根节点构建子树。

最后递归完成,树的构建就完成了。

梳理之后,我们要解决的主要问题就是,这个findMax,找到最大值方法该怎么实现呢?

很简单,有数组,也有开始和结束节点,那我们遍历数组就可以找到最大值了,为了方便下一次递归方法的使用,我们直接返回最大值的下标即可:

public int findMax(int[] nums, int l, int r) {
    int max = l;
    for (int i = l; i < r; i++) {
        if (nums[max] < nums[i])
            max = i;
        }
    return max;
}

还有一个问题需要解决,就是递归方法的终止条件,什么时候停止递归呢?

  • 自然就是当限定到区间数组为空的时候了。

比如:[3,2,1]

  • 我们传入的leftIndex=0,rightIndex=3,然后找到最大数组3。
  • 所以下一步递归方法中传入的leftIndex=0,rightIndex=0,区间数组为空,返回。

所以终止条件其实就是leftIndex = rightIndex,区间数组为空的时候。

if (l == r)
   return null;

最后的解法完整版如下:

public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return construct(nums, 0, nums.length);
    }
    public TreeNode construct(int[] nums, int l, int r) {
        if (l == r)
            return null;
        int max = findMax(nums, l, r);
        TreeNode root = new TreeNode(nums[max]);
        root.left = construct(nums, l, max);
        root.right = construct(nums, max + 1, r);
        return root;
    }
    public int findMax(int[] nums, int l, int r) {
        int max = l;
        for (int i = l; i < r; i++) {
            if (nums[max] < nums[i])
                max = i;
        }
        return max;
    }
}

复杂度

时间复杂度:O(n^2) 空间复杂度:O(n)

参考

https://leetcode-cn.com/problems/maximum-binary-tree

感谢大家的阅读,有一起学习的小伙伴可以关注下公众号—码上积木❤️ 每日一个知识点,建立完整体系架构。

本文分享自微信公众号 - 码上积木(Lzjimu),作者:积木zz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode - 最大二叉树

    原题地址:https://leetcode-cn.com/problems/maximum-binary-tree/

    晓痴
  • LeetCode题解—二叉树

    听名字还是比较好理解的,就是每个节点有两个分叉的树。但是又不要求一定有两个节点,只要小于等于2个节点就可以。

    码上积木
  • LeetCode 998. 最大二叉树 II

    向最大二叉树插入一个值; 如果该值大于根节点,则子树必须在该值的左边; 如果该值小于根节点,则该值必须在根节点的右子树

    Michael阿明
  • 【leetcode刷题】T117-二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    木又AI帮
  • LeetCode 654. 最大二叉树(递归)

    二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组...

    Michael阿明
  • 【Leetcode】二叉树的最大深度

    喜欢ctrl的cxk
  • LeetCode题解—重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    码上积木
  • LeetCode 二叉树系统题解

    TIPS:前中后序遍历区别在于三字中的中间那个字,前、中、后序分别对应左、根、右。

    Yano_nankai
  • Leetcode刷题记录:构建最大数二叉树

    给定一个不含重复数字的数组,最大二叉树构建规则如下: 1、根是数组中最大的数字 2、左边的子树是最大数字左边的内容 3、右边的子树是最大数字右边的内容

    大江小浪
  • Swift 二叉树的最大深度- LeetCode

    韦弦zhy
  • 【Leetcode】104. 二叉树的最大深度

    求最大深度,和深度相关,我们很容易想到用层序遍历。每遍历一层,就深度加1, 怎么记录是第几层我们之前的文章中讲过了。

    Leetcode名企之路
  • Leetcode 104. 二叉树的最大深度

    二叉树根节点为空,则树高度为 0,根节点不为空,则高度为左子树、右子树的最大值加一。

    zhipingChen
  • leetcode:104二叉树的最大深度

    思路:用深度优先遍历。 深度优先遍历是尽可能深的遍历这棵树。 怎么做? 新建一个变量记录每一个节点的层级,找到最大的层级即可。

    贵哥的编程之路
  • LeetCode 104. 二叉树的最大深度

    freesan44
  • LeetCode | 104.二叉树的最大深度

    这次来写一下 LeetCode 的第 104 题,二叉树的最大深度。

    码农UP2U
  • LeetCode题解—二叉树的镜像

    然后说个事,以后可能会减少算法题的文章了,因为我对于算法也没有很深的理解,只是和大家分享一下我刷题的过程,所以可能对大家的帮助不大。

    码上积木
  • ​LeetCode刷题实战98:验证二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • ​LeetCode刷题实战104:二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    程序IT圈
  • LeetCode刷题记录:104. 二叉树的最大深度

    英雄爱吃土豆片

扫码关注云+社区

领取腾讯云代金券