【LeetCode: 889. 根据前序和后序遍历构造二叉树 + DFS】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ DFS
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 889. 根据前序和后序遍历构造二叉树

⛲ 题目描述

给定两个整数数组,preorder 和 postorder ,其中 preorder 是一个具有 无重复 值的二叉树的前序遍历,postorder 是同一棵树的后序遍历,重构并返回二叉树。

如果存在多个答案,您可以返回其中 任何 一个。

示例 1:
在这里插入图片描述

输入:preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出:[1,2,3,4,5,6,7]
示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

提示:

1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都 不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都 不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

🌟 求解思路&实现代码&运行结果


⚡ DFS

🥦 求解思路
  1. 该题主要是通过前序和后序遍历来还原一颗二叉树,这也就导致这棵二叉树不一定是唯一的。
  2. 核心的思路:先在前序遍历中找到左子树的位置preorder[1],然后在后序遍历中找到对应的下标位置,对其加1得到左子树的大小,这就是突破点,根据左右子树分割前序和后序数组,左子树的前序数组取到的区间是[1,1+i),前序数组取到的区间是[1+i,n)。右子树的前序数组取到的区间是[0,i),前序数组取到的区间是[i,n-1)。对其左右子树递归这个过程,还原一颗二叉树。
  3. 有了基本的思路,接下来我们就来通过代码来实现一下递归和迭代的解法。
🥦 实现代码
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int n = preorder.length;
        if (n == 0) {
            return null;
        }
        if (n == 1) {
            return new TreeNode(preorder[0]);
        }
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 0;; i++) {
            if (postorder[i] == preorder[1]) {
                i = i + 1;// 下标加1
                root.left = constructFromPrePost(Arrays.copyOfRange(preorder, 1, 1 + i),
                        Arrays.copyOfRange(postorder, 0, i));
                root.right = constructFromPrePost(Arrays.copyOfRange(preorder, 1 + i, n),
                        Arrays.copyOfRange(postorder, i, n - 1));
                break;
            }
        }
        return root;
    }
}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

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

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

相关文章

研学活动报名平台系统功能清单

中小学生社会实践活动、研学旅行等素质教育活动报名与管理平台&#xff0c;功能包含&#xff1a;活动分类&#xff0c;活动管理&#xff0c;在线报名缴费&#xff0c;扫码核销&#xff0c;会员特权体系&#xff0c;在线商城&#xff0c;研学互动。系统支持入驻老师自行创建研学…

jenkins配置ssh的时候测试连接出现Algorithm negotiation fail

背景&#xff1a;当jenkins升级后&#xff0c;同时ssh插件也升级&#xff0c;测试ssh连接的时候 出现的问题&#xff1a; com.jcraft.jsch.JSchAlgoNegoFailException: Algorithm negotiation fail: algorithmName"server_host_key" jschProposal"ecdsa-sha2-n…

QSettings使用示例

解决的问题&#xff1a; 平常要存储一些临时数据&#xff0c;或者ini的系统参数数据&#xff0c;以下是源码解析 如何实现&#xff1a; 实现的UI如下 主要功能&#xff1a; 初始化&#xff1a; m_settings new QSettings("DParamSetting.ini", QSettings::IniFo…

springboot+vue项目基础开发(13)vue的注册页面

1创建页面 在view下面创建Login.vue 编写login.vue的代码 <script setup> import {User,Lock} from @element-plus/icons-vue import {ref } from vue&#

【JavaEE】_Servlet程序的编写方法

目录 1. 创建项目 2. 引入依赖 3. 创建目录结构 3.1 在main目录下创建一个webapp目录 3.2 在webapp目录下创建一个WEB-INF目录 3.3 在WEB-INF目录下创建一个web.xml文件 3.4 在web.xml中进行代码编写 4. 编写代码 4.1 在java目录下创建类 4.2 打印"hello world&…

代码随想录算法训练营第二十六天|39. 组合总和、40.组合总和II、131.分割回文串

39. 组合总和 刷题https://leetcode.cn/problems/combination-sum/description/文章讲解https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html视频讲解https://www.bilibili.com/video/BV1KT4y1M7HJ/?vd_sourceaf4853e80f89e28094a5fe1e220d9062 回溯…

vue+django+python办公耗材网上商城采购库存管理系统

办公耗材采购信息管理是信息行业业务流程过程中十分重要且必备的环节之一&#xff0c;在信息行业业务流程当中起着承上启下的作用&#xff0c;其重要性不言而喻。但是&#xff0c;目前许多信息行业在具体的业务流程处理过程中仍然使用手工操作的方式来实施&#xff0c;不仅费时…

C语言运用中断子系统用驱动控制led实验,c语言串口led点灯实验(驱动+应用层)

中断子系统用驱动控制led实验 驱动代码 #include <linux/init.h> #include <linux/module.h>#include<linux/interrupt.h> #include<linux/gpio.h> #include<linux/timer.h>#include<linux/of.h> #include<linux/of_irq.h> #inclu…

MySQL MGR 恢复(从库维度)

集群信息 一主两从 端口 角色 3307 主 3309 备 3303 备 从库故障 关掉 3303 从库 删除所有数据&#xff0c;模拟故障 从库恢复还原(物理备份恢复) 备份另一台 处于组关中的 从库的数据&#xff0c;端口为 3309 物理备份 xtrabackup --defaults-file/etc/my3309.cnf …

idea在工具栏中显示快速创建包和类的图标

一、效果图 点击需要创建包或者类的位置&#xff0c;在点击对用的图标就可以快速创建类或者包了。 二、设置 步骤一 View-->Appearance-->Toolbar 步骤二 File-->Settings-->Appearance & Behavior-->Menus and Toolbars-->Main Toolbar-->----…

路飞项目--06

redis介绍和安装 # 数据库&#xff1a; 关系型数据库&#xff1a;mysql、oracle、postgrasql、sqlserver、sqlite IBM&#xff1a;服务器 Oracle&#xff1a;数据库 达梦 EMC&#xff1a;存储 非关系型数据库: redis、mongodb、es…

数据库增删改查

DDL: 数据定义语言&#xff0c;用来定义数据库对象&#xff08;数据库、表、字段&#xff09;DML: 数据操作语言&#xff0c;用来对数据库表中的数据进行增删改DQL: 数据查询语言&#xff0c;用来查询数据库中表的记录DCL: 数据控制语言&#xff0c;用来创建数据库用户、控制数…

高录用快见刊【最快会后两个月左右见刊】第三届社会科学与人文艺术国际学术会议 (SSHA 2024)

第三届社会科学与人文艺术国际学术会议 (SSHA 2024) 2024 3rd International Conference on Social Sciences and Humanities and Arts *文章投稿均可免费参会 *高录用快见刊【最快会后两个月左右见刊】 重要信息 会议官网&#xff1a;icssha.com 大会时间&#xff1a;202…

基于生成扩散模型的分子对接程序-DiffDock安装及使用

欢迎浏览我的CSND博客&#xff01; Blockbuater_drug …点击进入 文章目录 前言一、DiffDock是什么&#xff1f;二、DiffDock安装步骤1. 下载2.创建conda环境并安装STEP 1. 创建conda环境并配置STEP 2. 配置ESM和OpenFoldSTEP 3. 检查cuda和pytorch geometric安装STEP 4. 检查p…

Linux:Jenkins用户权限和管理

1.下载插件 由于Jenkins的默认权限管理并不是很精细所以我们安装一个插件进行权限的一个管理 插件名称为&#xff1a;Role-based Authorization Strategy 安装完插件我们再去配置一下 进入全局安全配置 选择这个Role-Based Strategy策略然后保存 2.创建角色 我们这里主要使…

ArcgisForJS如何在线编辑ArcGIS Server发布的几何要素?

文章目录 0.引言1.ArcGIS创建几何要素2.ArcGIS Server发布几何要素3.ArcgisForJS在线编辑ArcGIS Server发布的几何要素 0.引言 ArcGIS For JS 是一种用于创建和编辑地理信息的 JavaScript 库&#xff0c;它允许用户在线编辑 ArcGIS Server 发布的几何要素。本文从ArcGIS创建几…

小程序--应用生命周期

小程序的应用周期处理逻辑都写在app.js中。 一、onLaunch 小程序启动时&#xff08;初始化完成&#xff09;执行&#xff0c;只执行一次。 常用于小程序更新&#xff0c;获取启动参数&#xff0c;获取场景值。 二、onShow 小程序启动&#xff0c;或从后台切换至前台时执行。 …

代码随想录算法训练营day20||二叉树part07、● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

530.二叉搜索树的最小绝对差 【需要领悟一下二叉树遍历上双指针操作&#xff0c;优先掌握递归】 给你一个二叉搜索树的根节点 root &#xff0c;返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数&#xff0c;其数值等于两值之差的绝对值。 思路 题目中要求在二叉…

第四十天| 343. 整数拆分、96.不同的二叉搜索树

Leetcode 343. 整数拆分 题目链接&#xff1a;343 整数拆分 题干&#xff1a;给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。 思考&#xff1a;动态规划。…

探索Promise异步模式抽象的变体——Promise.race篇

如果阅读有疑问的话&#xff0c;欢迎评论或私信&#xff01;&#xff01; 本人会很热心的阐述自己的想法&#xff01;谢谢&#xff01;&#xff01;&#xff01; 文章目录 前言初识Promise.race探索Promise.raceAPI实例 前言 在本栏前一篇Promise.all中&#xff0c;我们可以实…