力扣---从前序与中序遍历序列构造二叉树

给定两个整数数组 preorderinorder ,其中 preorder 是二叉树的先序遍历inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

示例 1:

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

示例 2:

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

解题思路:


链接:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solutions/107105/dong-hua-yan-shi-105-cong-qian-xu-yu-zhong-xu-bian/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty() || inorder.empty()) return nullptr;

        TreeNode * subroot = new TreeNode(preorder[0]);

        for(int i = 0; i < inorder.size() ; i++){
            if(inorder[i]==preorder[0]){
                vector<int> _pre(preorder.begin()+1,preorder.begin()+i+1);
                vector<int> pre_(preorder.begin()+i+1,preorder.end());

                vector<int> _in(inorder.begin(),inorder.begin()+i);
                vector<int> in_(inorder.begin()+i+1,inorder.end());

                subroot->left = buildTree(_pre,_in);
                subroot->right = buildTree(pre_,in_);

                break;
            }
        }
        return subroot;
    }
};

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

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

相关文章

IO——进程间通讯 IPC

1. 进程间通信方式 (1) 早期进程间通信&#xff1a; 无名管道(pipe)、有名管道(fifo)、信号(signal) (2) system V IPC&#xff1a; 共享内存(shared memory)、消息队列(message queue)、信号灯集(semaphore set) (3) BSD&#xff1a; 套接字(socket) 2. 无名管道 2.1特点 …

泛微E9开发 快速隐藏明细表列

快速隐藏明细表列 1、隐藏列方法&#xff08;不作用&#xff0c;一直隐藏&#xff09; 在实际运用中&#xff0c;用户不需要但是需要间接使用的列&#xff0c;我们可以通过右击该列-【列自定义属性】-在“列自定义属性”菜单中启用“隐藏列”功能。 根据该方法设置的前端页…

基于Springboot的社区疫情返乡管控系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的社区疫情返乡管控系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系…

OpenHarmony 上传和下载(API 10)教程~

介绍 本示例使用ohos.request接口创建上传和下载任务&#xff0c;实现上传、下载功能&#xff0c;hfs作为服务器&#xff0c;实现了文件的上传和下载和任务的查询功能。 效果预览 使用说明 1.本示例功能需要先配置服务器环境后使用&#xff0c;具体配置见上传下载服务配置。…

中颖51芯片学习7. printf重定向到串口与自定义日志输出函数

中颖51芯片学习7. printf重定向到串口与自定义日志输出函数 一、 printf 重定向1. 概念2. 实现方式3. C51 中printf数值格式化 二、日志函数1. 实现方案分析2. 代码&#xff08;1&#xff09;log_utils.h&#xff08;2&#xff09;main.c 3. 通过预定义宏实现日志分级输出&…

汇编语言88888

汇编语言安装指南 第一步&#xff1a;在github上下载汇编语言的安装包 网址&#xff1a;GitHub - HaiPenglai/bilibili_assembly: B站-汇编语言-pdf、代码、环境等资料B站-汇编语言-pdf、代码、环境等资料. Contribute to HaiPenglai/bilibili_assembly development by creat…

Flyweight 享元

意图 运用共享技术有效地支持大量细粒度的对象。 结构 其中 Flyweight描述一个接口&#xff0c;通过这个接口Flyweight可以接受并作用于外部状态。ConcreteFlyweight实现Flyweight接口&#xff0c;并作为内部状态&#xff08;如果有&#xff09;增加存储空间。ConcreteFlywe…

数字阅览室解决方案

一、方案概述 “数字阅览室”概念一经提出&#xff0c;就得到了广泛的关注&#xff0c;纷纷组织力量进行探讨、研究和开发&#xff0c;进行各种模型的试验。随着数字地球概念、技术、应用领域的发展&#xff0c;数字阅览室已成为数字地球家庭的成员&#xff0c;为信息高速公路…

vue3:树的默认勾选和全选、取消全选

实现的功能&#xff0c;上面有个选择框&#xff0c;当选中全部时&#xff0c;下方树被全选 代码&#xff1a; <template><div><el-select v-model"selectAll" style"margin-bottom: 10px;" change"handleSelectAllChange">&…

运行transformers报错check_min_version(“4.40.0.dev0“)

在huggingface &#xff08;transformers项目地址&#xff09;下载transformers的项目 并 python /transformers/examples/pytorch/language-modeling/run_clm.py 时报错 报错如下&#xff1a; 安装的 transformers 版本不对&#xff0c;这里安装了 4.39.3&#xff0c;实际想…

网站备案期间怎么关闭首页显示无法访问-文章及其它页面正常访问

自从做了开发者之后才发现每个人博主的需求都是不同的&#xff0c;的的确确颠覆了我的观点&#xff0c;无论是页面布局还是SEO相关的设置&#xff0c;可能是因为站点属性不同所以需求不同&#xff0c;慢慢的就会在主题加入一些自定接口来满足不同人的需求&#xff0c;有人需要P…

双链表的实现

我们知道链表其实有很多种&#xff0c;什么带头&#xff0c;什么双向啊&#xff0c;我们今天来介绍双向带头循环链表&#xff0c;了解了这个其他种类的链表就很简单了。冲冲冲&#xff01;&#xff01;&#xff01; 链表的简单分类 链表有很多种&#xff0c;什么带头循环链表&…

【c基础】文件操作

1.fopen和fclose函数 函数原型 FILE *fopen(const char *path, const char *mode); 参数解释&#xff1a; 返回值&#xff1a;fopen打开成功&#xff0c;则返回有效file的有效地址&#xff0c;失败返回NULL。path是文件路径&#xff0c;可以相对路径&#xff0c;可以绝对路径…

“手撕“三大特性之一的<继承>(上)

目录 一、为什么需要继承 二、什么是继承 三、继承怎么写 四、成员的访问 1.父类与子类的成员变量不同名 2.父类与子类的成员变量同名 3.父类与子类的成员方法不同名 4.父类与子类的成员方法同名 五、super关键字 一、为什么需要继承 先让我们看一段Java代码&#…

Unity地形关联出错的解决办法以及地形深度拷贝

问题 最近发现unity地形系统的一个bug&#xff0c;导入的场景地形数据关联错乱了&#xff0c;关联到别的场景的地形数据了&#xff0c;meta替换了也没用&#xff0c;不清楚它具体是怎么关联的。 看下面的案例&#xff1a; 可以看到正常这个场景的地形数据应该关联的是Scene_E…

力扣HOT100 - 142. 环形链表 II

解题思路&#xff1a; public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> set new HashSet<>();while (head ! null) {if (!set.add(head)) {return head;}head head.next;}return null;} }

文心一言 VS 讯飞星火 VS chatgpt (241)-- 算法导论17.3 7题

七、为动态整数多重集 S (允许包含重复值)设计一种数据结构&#xff0c;支持如下两个操作&#xff1a;① INSERT(S,x) 将 x 插入 S 中&#xff1b;② DELETE-LARGER-HALF(S) 将最大的 ⌈|S|/2⌉ 个元素从S中删除。解释如何实现这种数据结构&#xff0c;使得任意 m 个 INSERT 和…

Linux的firewalld防火墙

介绍firewalld&#xff1a; ①、firewalld&#xff08;Dynamic Firewall Manager of Linux systems&#xff0c;Linux系统的动态防火墙管理器&#xff09;服务是默认的防火墙配置管理工具&#xff0c;它拥有基于CLI&#xff08;命令行界面&#xff09;和基于GUI&#xff08;图…

Web Tours系统使用说明书

1.系统简介 产品名称&#xff1a;LoadRunner的Web Tours系统 产品功能&#xff1a;注册和登录用户信息、订票办理、退片办理、查询已定票信息、退出系统 系统默认用户&#xff1a;用户名jojo 密码&#xff1a;bean 2. 功能简介 2.1 注册用户信息 点击 sign up now&#xff…

(自学用)正演理论

基于波动方程如何解决数值频散问题——快速正演方法 NAD方法&#xff1a; 怎样离散/逼近高阶偏导数&#xff08;如何采样&#xff09;&#xff1a; 传统方法是用某一点及其周围点的函数f的线性组合来逼近导数。只有函数值&#xff0c;要想提高精度&#xff0c;压制数值频散就必…