当前位置: 首页 > news >正文

【数据结构】从前序与中序遍历,或中序与后序遍历序列,构造二叉树

欢迎浏览高耳机的博客

希望我们彼此都有更好的收获

感谢三连支持!

 

首先,根据先序遍历可以确定根节点E,再在中序遍历中通过E确定左树和右数 ;

设立inBegin和inEnd,通过这两个参数的游走,来进行子树的创建;

已知根节点,则左子树的范围表示为(inBegin,rootIndex - 1);

而右子树为(rootIndex + 1,inEnd);

通过递归调用,即可不断创建子树,直到叶子节点;

如果inBegin > inEnd,则说明此时为叶子节点,应该返回上一层递归;

public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChilde(preorder, inorder, 0, inorder.length-1);
}private TreeNode buildTreeChilde(int[] preorder, int[] inorder, int inBegin, int inEnd) {if(inBegin > inEnd){return null;}TreeNode root = new TreeNode(preorder[preIndex]); // 创建根节点int rootIndex = findRootIndex(inorder, inBegin, inEnd, preorder[preIndex]); // 找到根节点在中序遍历中的位置preIndex++;root.left = buildTreeChilde(preorder, inorder, inBegin, rootIndex-1); // 递归构建左子树root.right = buildTreeChilde(preorder, inorder, rootIndex+1, inEnd); // 递归构建右子树return root;
}private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key){for (int i = inBegin; i <= inEnd; i++) {if (key == inorder[i]) {return i;}}return -1;}

OJ链接:

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

 

同样的,根据后序遍历可以确定根节点,再在中序遍历中通过根节点确定左树和右数 ;

需要注意的是,由于postIndex根据后序遍历(左,右,根)创建,与前序遍历相反,所以每次递归时postIndex--,从根节点前的右子树开始递归;

同样的,已知根节点,则右子树表示范围为(rootIndex + 1,inEnd);

而左子树表示为(inBegin,rootIndex - 1);

通过递归调用,即可不断创建子树,直到叶子节点;

如果inBegin > inEnd,则说明此时为叶子节点,应该返回上一层递归;

 

public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length-1;return buildTreeChilde(inorder, postorder, 0, inorder.length-1);
}private TreeNode buildTreeChilde(int[] inorder, int[] postorder, int inBegin, int inEnd) {if(inBegin > inEnd){return null;}TreeNode root = new TreeNode(postorder[postIndex]); // 创建根节点int rootIndex = findRootIndex(inorder, inBegin, inEnd, postorder[postIndex]); // 找到根节点在中序遍历中的位置postIndex--;root.right = buildTreeChilde(inorder, postorder, rootIndex+1, inEnd); // 递归构建右子树root.left = buildTreeChilde(inorder, postorder, inBegin, rootIndex-1); // 递归构建左子树return root;
}private int findRootIndex(int[] inorder, int inBegin, int inEnd, int key){for (int i = inBegin; i <= inEnd; i++) {if (key == inorder[i]) {return i;}}return -1;}

OJ链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/ 


希望这篇博客能为你理解java编程思想提供一些帮助。

如有不足之处请多多指出。

我是高耳机。 

相关文章:

【数据结构】从前序与中序遍历,或中序与后序遍历序列,构造二叉树

欢迎浏览高耳机的博客 希望我们彼此都有更好的收获 感谢三连支持&#xff01; 首先&#xff0c;根据先序遍历可以确定根节点E&#xff0c;再在中序遍历中通过E确定左树和右数 &#xff1b; 设立inBegin和inEnd&#xff0c;通过这两个参数的游走&#xff0c;来进行子树的创建&a…...

ARM公司发展历程

Arm从1990年成立前开始&#xff0c;历经漫长岁月树立各项公司里程碑及产品成就&#xff0c;一步步成为全球最普及的运算平台。 添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09; Acorn 时期 1978年&#xff0c;Chris Curry和Hermann Hauser共同创立了Acorn…...

C# :IQueryable IEnumerable

文章目录 1. IEnumerable2. IQueryable3. LINQ to SQL4. IEnumerable & IQueryable4.1 Expression4.2 Provider 1. IEnumerable namespace System.Collections: public interface IEnumerable {public IEnumerator GetEnumerator (); }public interface IEnumerator {pubi…...

三、生成RPM包

文章目录 1、编译生成so、bin 通过此工程编译生成so\bin文件 2、将so\bin打包到rpm中 ###### 1.生成可执行文件、库文件 ######### cmake_minimum_required(VERSION 3.15)project(compute) set(target zls_bin) set(target2 libcompute.so) # 依赖的头文件 include_directori…...

单实例11.2.0.4迁移到11.2.0.4RAC_使用rman异机恢复

保命法则&#xff1a;先备份再操作&#xff0c;磁盘空间紧张无法备份就让满足&#xff0c;给自己留退路。 场景说明&#xff1a; 1.本文档的环境为同平台、不同版本&#xff08;操作系统版本可以不同&#xff0c;数据库版本相同&#xff09;&#xff0c;源机器和目标机器部分…...

MySQL之查询性能优化(二)

查询性能优化 慢查询基础:优化数据访问 查询性能低下最基本的原因是访问的数据太多。某些查询可能不可避免地需要筛选大量数据&#xff0c;但这并不场景。大部分性能低下的查询都可以通过减少访问的数据量的方式进行优化。对于低效的查询&#xff0c;我们发现通过下面两个步骤…...

The Best Toolkit 最好用的工具集

The Best Toolkit 工欲善其事&#xff0c;必先利其器&#xff0c;整理过往工作与生活中遇到的最好的工具软件 PDF合并等 PDF24 Tools PDF查看器 SumatraPDF 可以使用黑色来查看&#xff0c;相对不伤眼睛&#xff0c;也有电子书相关的阅读器 Kindle pdf裁边工具 briss 软件卸载…...

使用C#反射中的MAKEGENERICTYPE函数,来为泛型方法和泛型类指定(泛型的)类型

MakeGenericType 是一个在 C# 中用于创建开放类型的实例的方法。开放类型是一种未绑定类型参数的泛型类型。当你有一个泛型类型定义&#xff0c;并且想要用特定的类型实例化它时&#xff0c;你可以使用 MakeGenericType 方法。 public Type MakeGenericType (params Type[] ty…...

sql注入 (运用sqlmap解题)

注:level参数 使用–batch参数可指定payload测试复杂等级。共有五个级别&#xff0c;从1-5&#xff0c;默认值为1。等级越高&#xff0c;测试的payload越复杂&#xff0c;当使用默认等级注入不出来时&#xff0c;可以尝试使用–level来提高测试等级。 --level 参数决定了 sql…...

HTML5 Canvas 绘图教程二

在本教程中&#xff0c;我们将探讨 canvas 的高级用法&#xff0c;包括复杂的绘图 API、坐标系统和变换操作、平滑动画技术以及复杂应用和游戏开发的实践。 1. 绘图 API 高级方法 1.1 二次贝塞尔曲线 (quadraticCurveTo) 二次贝塞尔曲线需要两个点&#xff1a;一个控制点和一…...

Linux 命令 find 的深度解析与使用

Linux 命令 find 的深度解析与使用 在 Linux 系统中&#xff0c;find 命令是一个功能强大的工具&#xff0c;用于在文件系统中搜索文件或目录。无论是基于文件名、文件类型、文件大小、文件权限&#xff0c;还是基于文件的最后修改时间等&#xff0c;find 命令都能提供灵活的搜…...

字符串操作记录

1 拼接 Concat():拼接字符串 Let stringvalue “hello ”; Let result stringvalue.concat(“world”) Console.log(result) // “hello world” 2 删 Let stringvalue “hello world”Console.log(stringvalue.slice(3)); // ‘lo world’Console.log(stringvalue.subst…...

【python科学文献计量】关于中国知网检索策略的验证,以事故伤害严重程度检索为例

关于中国知网检索策略的验证,以事故伤害严重程度检索为例 1 背景2 文献下载3 数据处理1 背景 由于要进行相关研究内容的综述,需要了解当前我国对于事故伤害严重程度的研究现状,采用国内较为知名的检索网站(中国知网)进行文献数据集检索 由于最近知网出bug,检索的结果在…...

AdminController

目录 1、 AdminController 1.1、 UpdateFaculty 1.1.1、 // Check if a new image file is provided 1.1.2、 // CHECKING FOLDER EXIST OR NOT - IF NOT THEN CREATE F0LDER 1.1.3、 // READY SEND PATH TO IMAGE TO DB 1.1.4、 DeleteFaculty 1.1.5、 // If th…...

Vue3-Pinia状态管理器

Pinia 是 Vue 的专属状态管理库&#xff0c;它允许你跨组件或页面共享状态。如果你熟悉组合式 API 的话&#xff0c;你可能会认为可以通过一行简单的 export const state reactive({}) 来共享一个全局状态。对于单页应用来说确实可以&#xff0c;但如果应用在服务器端渲染&…...

安装存储器的段描述符并加载GDTR

代码清单 ;代码清单12-1;文件名&#xff1a;c12_mbr.asm;文件说明&#xff1a;硬盘主引导扇区代码;创建日期&#xff1a;2011-5-16 19:54&#xff1b;修改于2022-02-16 11:15;设置堆栈段和栈指针mov ax, csmov ss, axmov sp, 0x7c00;计算GDT所在的逻辑段地址12 mov ax, [c…...

2024年5月架构试题

2024年5月份架构师考试真题完整版 截至2024-5-28 19:24:14已全部收录完成 共75道选择题&#xff0c;5道案例题&#xff0c;4道论文题。题目顺序不分先后。 全网最全的2024年5月份架构师考试真题回忆版&#xff0c;包含答案和解析。 选择题 计算机基础 操作系统调度算法 选先来先…...

品牌控价的同时也要做好数据分析

品牌在进行电商价格监测时&#xff0c;确实不应仅停留在收集低价数据的层面。在数据量巨大的今天&#xff0c;如何深度分析和挖掘这些数据的价值&#xff0c;为品牌的决策和战略提供有力支持&#xff0c;显得尤为重要。 首先&#xff0c;电商数据的监测和分析有助于品牌更全面…...

微服务学习Day11-缓存问题学习

文章目录 多级缓存引入JVM进程缓存导入商品案例Caffeine学习实现进程缓存 Lua语法入门认识Lua变量和循环条件控制、函数 多级缓存安装OpenRestyOpenResty入门请求参数处理查询TomcatRedis缓存预热查询Redis缓存Nginx本地缓存 缓存同步策略策略安装Canal监听Canal 多级缓存引入 …...

虚拟化知识学习

虚拟化知识学习 关键概念和术语的简要介绍 虚拟化的基本概念 虚拟机 (VM)&#xff1a;一个虚拟机是一个模拟计算机系统的环境。它运行在物理硬件之上&#xff0c;但与物理硬件隔离&#xff0c;提供类似于物理计算机的功能。 虚拟化技术&#xff1a;这是指使用软件来创建虚拟版…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...

【iOS】 Block再学习

iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...

【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验

2024年初&#xff0c;人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目&#xff08;一款融合大型语言模型能力的云端AI编程IDE&#xff09;时&#xff0c;技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力&#xff0c;TRAE在WayToAGI等…...