LeetCode 106 从中序与后序遍历序列构造二叉树

根据中序遍历和后序遍历的性质,还原二叉树,详细见注释 

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        //空,直接返回null
        if(inorder.size() == 0) return nullptr;
        //一个,返回一个node结点
        if(inorder.size() == 1) return new TreeNode(inorder[0]);
        int size = postorder.size();
        int val = postorder[size-1];
        //后续遍历的最后一个元素是根节点
        TreeNode* root = new TreeNode(val);
        //在中序中找到根节点的位置
        auto idx1 = find(inorder.begin(), inorder.end(), val);
        //中序遍历中根节点的位置左侧是左子树中序遍历,右侧为右子树中序遍历
        //分别拷贝构造出新的中序遍历vector
        vector<int> inorder_left(inorder.begin(), idx1);
        vector<int> inorder_right(idx1+1, inorder.end());
        int left_num = inorder_left.size();
        //后序遍历左子树等于后序遍历起点+中序遍历左子树vector.size()
        vector<int> postorder_left(postorder.begin(), postorder.begin()+left_num);
        //后边遍历右子树等于后序遍历左子树下一个元素到倒数第二个元素
        vector<int> postorder_right(postorder.begin()+left_num, postorder.end()-1);
        
        //构造左右子树
        root->left = buildTree(inorder_left, postorder_left);
        root->right = buildTree(inorder_right, postorder_right);
        return root;
    }

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

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

相关文章

数据结构与算法-动态规划-最长回文子串

最长回文子串 给你一个字符串 s&#xff0c;找到 s 中最长的回文子串。 示例 1&#xff1a; 输入&#xff1a;s "babad" 输出&#xff1a;"bab" 解释&#xff1a;"aba" 同样是符合题意的答案。示例 2&#xff1a; 输入&#xff1a;s "…

识图ACWP.BCWS.BCWP

将三个概念想象成三个角色&#xff08;如&#xff1a;勇士、法师、盗贼&#xff09;&#xff0c;其中&#xff1a; ACWP是勇士&#xff0c;代表实际力量&#xff08;实际成本&#xff09;&#xff1b;BCWS是法师&#xff0c;代表预期魔法&#xff08;预算成本工作量预测&#x…

vscode移动侧边栏到右边

vscode移动侧边栏到右边&#xff0c;的简单办法 直接在侧栏上单击右键&#xff0c;选择向右移动主侧栏

有哪些好的 Stable Diffusion 提示词(Prompt)可以参考?

Docker 作图咒语生成器 docker-prompt-generator 是一个开源项目&#xff0c;可以利用模型反推出提示词&#xff0c;让你偷偷懒&#xff0c;无需琢磨怎么写prompt&#xff0c;只需要找一个差不多的模型反推一下&#xff0c;直接用就好了&#xff0c;支持支持 MidJourney、Stab…

Go - 9.struct 使用指南

目录 一.引言 二.struct 定义 三.struct 实践 1. 初始化 struct 2. 嵌套 struct 3. func 与 struct 四.struct 进阶 1.Json Tags 2.Other Tags 五.总结 一.引言 在编程中&#xff0c;结构体&#xff08;struct&#xff09;是一种聚合数据类型&#xff0c;用于将多个…

文献解读-长读长测序-第十四期|《作为了解棉花驯化的资源,印度棉(Gossypium herbaceum L. Wagad)基因组》

关键词&#xff1a;基因组&#xff1b;长读长测序&#xff1b;棉花基因组&#xff1b; 文献简介 标题&#xff08;英文&#xff09;&#xff1a;The Gossypium herbaceum L. Wagad genome as a resource for understanding cotton domestication标题&#xff08;中文&#xff…

【HTML入门】列表与表格

文章目录 前言一、列表与表格是什么&#xff1f;列表表格 二、使用标签列表标签表格标签 三、组合情况列表的组合表格的组合 四、示例代码总结 好的&#xff0c;以下是一个关于HTML列表与表格的文章示例&#xff1a; 前言 随着网页开发的普及&#xff0c;HTML成为了构建网页的…

零基础学习MySQL---MySQL入门

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、什么是数据库 问&#xff1a;存储数据用文件就可以了&#xff0c;为什么还要弄个数据库呢&#xff1f; 这就不得不提…

Java面试八股文

一、Redis 1. 使用场景 &#xff08;1&#xff09;Redis的数据持久化策略有哪些 RDB&#xff1a;全称Redis Database Backup file&#xff08;Redis数据备份文件&#xff09;&#xff0c;也被叫作Redis数据快照。简单来说就是把内存中的所有数据都记录到磁盘中。当Redis实例故…

Chapter9 更复杂的光照——Shader入门精要学习笔记

Chapter9 更复杂的光照 一、Unity的渲染路径1.渲染路径的概念2.渲染路径的类型①前向渲染路径a. 前向渲染路径的原理b. Unity中的前向渲染c. 两种Pass ②延迟渲染路径a. 延迟渲染路径的原理b. Unity中的延迟渲染c. 两种Pass ③顶点照明渲染路径 二、Unity的光源类型1.光源类型①…

毫秒级相应逆流检测电表安科瑞防逆流电能表

家庭储能系统 生态环境与人们的日常生活密切相关&#xff0c;越来越多的家庭开始重视居住环境的绿色、环保、智能及可持续性&#xff0c;并采取具体行动。截至2023年&#xff0c;欧洲太阳能发电容量已超200GW&#xff0c;家庭储能系统的安装量呈爆炸性增长。 用户痛点及需求 …

前端基础:JavaaScript(篇二)

目录 内置对象 String字符串 属性 代码 运行 方法 代码 运行 日期 代码 运行 Math 代码 运行 数组 定义 属性 代码 运行 方法 join(分隔符>) &#xff1a; 代码 运行 reverse()&#xff1a; 代码 运行 sort() &#xff1a; 代码 运行 事件 …

有哪些手持小风扇品牌推荐?五大手持小风扇诚意推荐!

在炎炎夏日&#xff0c;一款便携且高效的手持小风扇无疑是消暑的必备神器。为了帮助大家轻松应对酷暑&#xff0c;我们精心挑选了五大手持小风扇品牌进行诚意推荐。这些品牌不仅拥有出色的降温效果&#xff0c;更在外观设计、便携性、续航能力及操作便捷性上表现卓越。接下来&a…

电子邮件OTP验证身份认证接口API服务商比较

电子邮件OTP验证身份认证接口API服务商如何正确选择&#xff1f; 电子邮件OTP验证是一种广泛应用且安全的身份认证方式。AokSend将比较几家主要的电子邮件OTP验证身份认证接口API服务商&#xff0c;帮助企业选择合适的解决方案。 电子邮件OTP&#xff1a;验证优势 可以为用户…

软考高级-系统分析师知识点100条速记!

宝子们&#xff01;上半年软考已经结束一段时间了&#xff0c;准备备考下半年软考高级-系统分析师的小伙伴可以开始准备了&#xff0c;毕竟高级科目的难度可是不低的&#xff0c;相信参加过上半年系分的小伙伴深有体会。 这里给大家整理了100条系分知识点&#xff0c;涵盖全书9…

【SPIE独立出版】第四届智能交通系统与智慧城市国际学术会议(ITSSC 2024)

第四届智能交通系统与智慧城市国际学术会议&#xff08;ITSSC 2024&#xff09;将于2024年8月23-25日在中国西安举行。本次会议主要围绕智能交通、交通新能源、无人驾驶、智慧城市、智能家居、智能生活等研究领域展开讨论&#xff0c; 旨在为该研究领域的专家学者们提供一个分享…

如何在 Java 应用中使用 Jedis 客户端库来实现 Redis 缓存的基本操作

本人详解 作者:王文峰,参加过 CSDN 2020年度博客之星,《Java王大师王天师》 公众号:JAVA开发王大师,专注于天道酬勤的 Java 开发问题中国国学、传统文化和代码爱好者的程序人生,期待你的关注和支持!本人外号:神秘小峯 山峯 转载说明:务必注明来源(注明:作者:王文峰…

【kubernetes】资源调度综合篇,HPA自动扩/缩容等功能

一、标签和选择器 1、标签 命令行操作 # 查看标签 kubectl get [资源类型] [资源名] --show-labels# 修改标签 kubectl label [资源类型] [资源名] [标签名][标签值] --overwrite# 创建标签 kubectl label [资源类型] [资源名] [标签名][标签值]Yalm文件操作 2、选择器 命…

十三、【源码】自动扫描注册Bean

源码地址&#xff1a;https://github.com/spring-projects/spring-framework 仓库地址&#xff1a;https://gitcode.net/qq_42665745/spring/-/tree/13-auto-scan-bean 自动扫描注册Bean 自动扫描Bean流程&#xff1a; 配置文件中配置标签<context:component-scan base-…