LeetCode题练习与总结:从中序与后序遍历序列构造二叉树--106

一、题目描述

给定两个整数数组 inorderpostorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

示例 2:

输入:inorder = [-1], postorder = [-1]
输出:[-1]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

二、解题思路

  1. 后序遍历的最后一个元素是树的根节点。
  2. 在中序遍历中找到根节点的位置,可以将中序遍历分成左右两个子树。
  3. 根据中序遍历中左右子树的长度,可以将后序遍历也分成左右两个子树。
  4. 递归地对左右子树进行上述步骤,构建出整棵树。

三、具体代码

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return buildTree(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode buildTree(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd) {
        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }

        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        int index = indexMap.get(rootVal);

        int leftSize = index - inStart;
        int rightSize = inEnd - index;

        root.left = buildTree(postorder, postStart, postStart + leftSize - 1, inorder, inStart, index - 1);
        root.right = buildTree(postorder, postStart + leftSize, postEnd - 1, inorder, index + 1, inEnd);

        return root;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度
  • 构建索引映射表 indexMap 需要 O(n) 的时间,其中 n 是中序遍历的长度。
  • 递归函数 buildTree 对于每个节点都会被调用一次,每次调用都会处理一个子树,子树的规模随层数减小而减小。在最坏的情况下,每次递归都会将问题规模减半,因此递归的深度为 O(log n),但由于每次递归都需要进行一些常数时间的操作,所以每次递归的时间复杂度为 O(1)。因此,整个递归过程的时间复杂度为 O(n)。
  • 综上,整个算法的时间复杂度为 O(n)。
2. 空间复杂度
  • 索引映射表 indexMap 需要存储 n 个元素,因此空间复杂度为 O(n)。
  • 递归调用栈的最大深度为树的高度,最坏情况下树完全不平衡,高度为 O(n),因此递归的最大空间复杂度为 O(n)。
  • 综上,整个算法的空间复杂度为 O(n)。

五、总结知识点

  1. 哈希表(HashMap):用于存储中序遍历中每个值对应的索引,以便快速查找根节点在中序遍历中的位置。

  2. 递归:构建二叉树的过程是通过递归函数 buildTree 实现的,每次递归处理一个子树,直到子树为空。

  3. 二叉树的构建:理解二叉树的结构和构建过程,以及中序遍历和后序遍历的特点。

  4. 数组的索引操作:通过数组的索引来访问和操作数组中的元素,以及计算子数组的长度和位置。

  5. 树的节点定义:使用 TreeNode 类来定义树的节点,每个节点包含值 val 和指向左右子节点的引用 left 和 right

  6. 函数的定义和调用:定义了两个函数 buildTree 和 buildTree(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd),并理解它们之间的调用关系。

  7. 边界条件的判断:在递归函数中,首先检查递归的基本情况(即递归的终止条件),如果 postStart > postEnd || inStart > inEnd,则返回 null

  8. 分治思想:将大问题分解为小问题来解决,这里是根据中序遍历和后序遍历的特点,将问题分解为构建左右子树的问题。

以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/641620.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【百度云千帆AppBuilder】诗词达人:AI引领的诗词文化之旅

文章目录 写在前面&#xff1a;百度云千帆AppBuilder诗词达人&#xff1a;AI引领的诗词文化之旅功能介绍&#xff1a;诗词达人智能体的深度体验1. 诗词接龙学习2. 诗词深度解析3. 互动式问答4. 诗词创作辅助 技术特点详解&#xff1a;"诗词达人"智能体的创新技术零代…

【论文笔记】Layer-Wise Weight Decay for Deep Neural Networks

Abstract 本文为了提高深度神经网络的训练效率&#xff0c;提出了逐层权重衰减(layer-wise weight decay)。 本文方法通过逐层设置权重衰减稀疏的不同值&#xff0c;使反向传播梯度的尺度与权重衰减的尺度之比在整个网络中保持恒定。这种设置可以避免过拟合或欠拟合&#xff0…

胶原蛋白流失大揭秘:你的肌肤还年轻吗?

&#x1f343;当我们谈及胶原蛋白&#xff0c;不少女生眼中都会闪过一丝光芒。为什么呢&#xff1f;因为胶原蛋白是维持我们肌肤弹性、水润的秘密武器啊&#xff01;但是&#xff0c;随着岁月的流逝&#xff0c;你是否发现自己的肌肤开始变得松弛、无弹性&#xff0c;甚至出现了…

亚马逊测评技术自己掌控:打造爆款产品,快速突破销量瓶颈

不管新老店铺来说&#xff0c;出单都是至关重要的&#xff0c;在我们的理解当中测评应该是一种成长剂&#xff0c;是一个加快店铺成长的工具&#xff0c;因为它在店铺的破0、突破瓶颈期、引爆爆款以及在后期店铺的一个补量上都会有一个明显的作用 测评有什么意义&#xff1f; …

Vue实现二维码的展示及下载

个人介绍 hello hello~ &#xff0c;这里是 code袁~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的…

amtlib.dll打不开怎么办?一键修复丢失amtlib.dll方法

电脑丢失amtlib.dll文件是什么情况&#xff1f;出现amtlib.dll打不开怎么办&#xff1f;这样的情况有什么解决方法呢&#xff1f;今天就和大家聊聊amtlib.dll文件同时教大家一键修复丢失amtlib.dll方法&#xff1f;一起来看看amtlib.dll文件丢失会有哪些方法修复&#xff1f; a…

新手做抖音小店应该注意哪些问题?怎么正确的做抖音小店?

大家好&#xff0c;我是电商花花。 我们想做好一家抖音小店&#xff0c;想长期持久的做好一家抖店&#xff0c;一定要注意下面这些问题&#xff0c;只有避开这些做店的坑&#xff0c;我们才能稳稳的出单&#xff0c;稳稳的赚钱。 做抖音小店不能无脑铺货&#xff0c;要做精细…

HarmonyOS 鸿蒙应用开发 - 创建自定义组件

开发者定义的称为自定义组件。在进行 UI 界面开发时&#xff0c;通常不是简单的将系统组件进行组合使用&#xff0c;而是需要考虑代码可复用性、业务逻辑与UI分离&#xff0c;后续版本演进等因素。因此&#xff0c;将UI和部分业务逻辑封装成自定义组件是不可或缺的能力。 1、创…

SpringBoot3.x 整合 Spring AI

Spring AI 已经发布了一段时间&#xff0c;虽然推出的时候就被人说只是一个套了 API 的壳&#xff0c;但是作为 Spring 生态的一个开源项目&#xff0c;用它来结合到现有业务系统中还是一个比较好的方案&#xff0c;毕竟像笔者当初为了接入 OpenAI 的 API&#xff0c;还专门学了…

链路初始化和训练

一、总览 链路初始化和训练&#xff0c;由物理层进行控制&#xff0c;是一个基于硬件的过程。初始化设备的链路和端口&#xff0c;使得设备能够收发报文&#xff0c;在链路上正常通信。 在reset后由硬件自动启动完整的训练过程&#xff0c;并由LTSSM管理。 1 位锁定 训练开始…

【正点原子Linux连载】 第四十六章 M.2硬盘驱动实验摘自【正点原子】ATK-DLRK3568嵌入式Linux驱动开发指南

1&#xff09;实验平台&#xff1a;正点原子ATK-DLRK3568开发板 2&#xff09;平台购买地址&#xff1a;https://detail.tmall.com/item.htm?id731866264428 3&#xff09;全套实验源码手册视频下载地址&#xff1a; http://www.openedv.com/docs/boards/xiaoxitongban 第四十…

揭秘循环购模式:消费返利新玩法,引领电商新潮流

在当今的消费市场中&#xff0c;有一种商业模式引起了广大消费者的热烈讨论——那就是循环购模式。你可能会想&#xff0c;消费满千元就能得到两千元的福利&#xff0c;每天还能领取现金&#xff0c;这怎么可能呢&#xff1f;商家难道真的在“慷慨解囊”&#xff1f;今天&#…

7.2k star的万能视频解析下载插件

今天给大家介绍一个超级厉害的浏览器插件&#xff0c;可以解析各个平台网页视频——猫抓。 项目简介 猫抓&#xff08;cat-catch&#xff09; 是一款资源嗅探扩展插件&#xff0c;他能够帮助你筛选列出当前页面的资源。简单来说&#xff0c;当你打开任意一个带有视频的网页&a…

Vue3中为Ant Design Vue中table的checkbox加tooltip、popover

问题的产生 Vue版本&#xff1a;3.3.13 ant-design-vue 版本&#xff1a;3.x.x 在工作时遇到一个场景&#xff0c;需要在 ant-table 的 checkbox 被禁用的时候提示原因&#xff0c;但是在 ant-design-vue 文档中并没有发现有相关介绍。 首先我去看了issue中是否有提到相关问题…

【MATLAB源码-第214期】基于matlab的遗传算法GA最短路径路由优化算法仿真。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 在现代网络通信和路径规划领域&#xff0c;最短路径路由优化算法是一项关键技术。它涉及在给定的网络拓扑中寻找从源点到目标点的最短或成本最低的路径。近年来&#xff0c;遗传算法&#xff08;GA&#xff09;因其出色的全局…

2024.05.18学习记录

1、Vue3 Composition API Vite jsx 2、react 基本使用、高级用法 3、刷题&#xff1a;回溯部分剩下的题目

轻松拿捏C语言——【字符串函数】的使用及模拟实现

&#x1f970;欢迎关注 轻松拿捏C语言系列&#xff0c;来和 小哇 一起进步&#xff01;✊ &#x1f389;创作不易&#xff0c;请多多支持&#x1f389; &#x1f308;感谢大家的阅读、点赞、收藏和关注&#x1f495; &#x1f339;如有问题&#xff0c;欢迎指正 感谢 目录 一、…

java学习四

Random 随机数 数组 静态初始化数组 数组在计算机中的基本原理 数组的访问 什么是遍历 数组的动态初始化 动态初始化数组元素默认值规则 Java内存分配介绍 数组在计算机中的执行原理 使用数组时常见的一个问题 案例求数组元素最大值 public class Test1 {public static void ma…

香蕉成熟度检测YOLOV8NANO

香蕉成熟度检测YOLOV8NANO&#xff0c;采用YOLOV8NANO训练&#xff0c;得到PT模型&#xff0c;然后转换成ONNX模型&#xff0c;让OEPNCV调用&#xff0c;从而摆脱PYTORCH依赖&#xff0c;支持C。python&#xff0c;安卓开发。能检测六种香蕉类型freshripe freshunripe overripe…

Home Credit - Credit Risk Model Stability

本篇是对Kaggle上Home Credit - Credit Risk Model Stability竞赛中的开源代码VotingClassifier Home Credit的解读。原链接在VotingClassifier Home Credit (kaggle.com)。 %%writefile script.py import sys from pathlib import Path import subprocess import os import g…