22_最大二叉树

简介: 22_最大二叉树

654. 最大二叉树

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

  1. 创建一个根节点,其值为 nums 中的最大值。
  2. 递归地在最大值 左边子数组前缀上 构建左子树。
  3. 递归地在最大值 右边子数组后缀上 构建右子树。

返回 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] 。
    - [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
        - 空数组,无子节点。
        - [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
            - 空数组,无子节点。
            - 只有一个元素,所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
        - 只有一个元素,所以子节点是一个值为 0 的节点。
        - 空数组,无子节点。

示例 2:

输入:nums = [3,2,1]
输出:[3,null,2,null,1]

[思路]

构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。

  • 确定递归函数的参数和返回值
    参数传入的是存放元素的数组,返回该数组构造的二叉树的头结点,返回类型是指向节点的指针。
TreeNode constructMaximumBinaryTree(int[] nums);
  • 确定终止条件
    题目中说了输入的数组大小一定是大于等于1的,所以我们不用考虑小于1的情况,那么当递归遍历的时候,如果传入的数组大小为1,说明遍历到了叶子节点了。
    那么应该定义一个新的节点,并把这个数组的数值赋给新的节点,然后返回这个节点。 这表示一个数组大小是1的时候,构造了一个新的节点,并返回。
TreeNode node = new TreeNode(0);
if (nums.length == 1) {
  node.val = nums[0];
  return node;
}
  • 确定单层递归的逻辑
    1、先要找到数组中最大的值和对应的下标,最大的值构造根节点,下标用来下一步分割数组。
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < nums.length; i++) {
  if(nums[i] > maxValue) {
    maxValue = nums[i];
    maxValueIndex = i;
  }
}
TreeNode root = new TreeNode(maxValue);
  • 2、最大值所在的下标左区间构造左子树
    这里要判断maxValueIndex > 0,因为要保证左区间至少有一个数值。
if (maxValueIndex > 0) {
  node.left = constructMaximumBinaryTree(nums, leftIndex, maxValueIndex);
}
  • 3、最大值所在的下标右区间构造右子树
    判断maxValueIndex < (nums.size() - 1),确保右区间至少有一个数值。
if (maxValueIndex < (nums.size() - 1)) {
    node.right = constructMaximumBinaryTree(nums, maxValueIndex, nums.length);
}
  • 综合代码如下:
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }
    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {  // 没有元素了
            return null;
        }
        if (rightIndex - leftIndex == 1) { //只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;  // 最大值的数组下标
        int maxValue = nums[maxIndex];  // 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxValue) {
                maxIndex = i;
                maxValue = nums[i];
            }
        }
        TreeNode root = new TreeNode(maxValue);
        // 根据maxIndex划分左右子树
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }
}
相关文章
|
存储 Android开发
Rockchip系列之客制化GPIO接口Driver部分(2)
Rockchip系列之客制化GPIO接口Driver部分(2)
274 0
|
SQL 分布式计算 Java
Spark入门指南:从基础概念到实践应用全解析
在这个数据驱动的时代,信息的处理和分析变得越来越重要。而在众多的大数据处理框架中, Apache Spark 以其独特的优势脱颖而出。
389 0
|
8月前
|
缓存 监控 安全
高并发编程知识体系
本文将从线程的基础理论谈起,逐步探究线程的内存模型,线程的交互,线程工具和并发模型的发展。扫除关于并发编程的诸多模糊概念,从新构建并发编程的层次结构。
|
7月前
|
算法
一次推理,实现六大3D点云分割任务!华科发布大一统算法UniSeg3D,性能新SOTA
华中科技大学研究团队提出了一种名为UniSeg3D的创新算法,该算法通过一次推理即可完成六大3D点云分割任务(全景、语义、实例、交互式、指代和开放词汇分割),并基于Transformer架构实现任务间知识共享与互惠。实验表明,UniSeg3D在多个基准数据集上超越现有SOTA方法,为3D场景理解提供了全新统一框架。然而,模型较大可能限制实际部署。
453 15
|
数据可视化 Python
Python模型评估与选择:面试必备知识点
【4月更文挑战第17天】本文深入探讨了Python模型评估与选择在面试中的关键点,包括性能度量、过拟合与欠拟合识别、模型比较与选择、模型融合和偏差-方差权衡。强调了避免混淆评估指标、忽视模型验证和盲目追求高复杂度模型的常见错误,并提供相关代码示例,如交叉验证、网格搜索和超参数调优。通过理解这些概念和技巧,可在面试中展示出色的数据科学能力。
367 12
|
SQL 机器学习/深度学习 算法
【python】python指南(五):静态类型注解之List
【python】python指南(五):静态类型注解之List
151 0
【python】python指南(五):静态类型注解之List
|
存储 监控 安全
JVM工作原理与实战(五):类的生命周期-加载阶段
JVM作为Java程序的运行环境,其负责解释和执行字节码,管理内存,确保安全,支持多线程和提供性能监控工具,以及确保程序的跨平台运行。本文主要介绍了类的生命周期、类的加载阶段等内容。
160 5
|
存储 供应链 安全
区块链技术在供应链管理中的透明性与可追溯性研究
区块链技术在供应链管理中的透明性与可追溯性研究
|
供应链 JavaScript 前端开发
25个常见的python系统设计源码(python+mysql+vue)
25个常见的python系统设计源码(python+mysql+vue)
421 3
|
C语言
日常知识点之编译运行时识别头文件目录或者链接库目录设置
日常知识点之编译运行时识别头文件目录或者链接库目录设置
184 0