LeetCode 0105.从前序与中序遍历序列构造二叉树:分治(递归)——五彩斑斓的题解(若不是彩色的可以点击原文链接查看)

【LetMeFly】105.从前序与中序遍历序列构造二叉树:分治(递归)——五彩斑斓的题解(若不是彩色的可以点击原文链接查看)

力扣题目链接:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

给定两个整数数组 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]

 

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

方法一:分治(递归)

  • 前序遍历: 左子树 右子树
  • 中序遍历:左子树 右子树

写一个函数dfs接收前序遍历数组中序遍历数组作为参数:

  1. 根据前序遍历数组的第一个元素为根节点建立节点
  2. 找到根节点在中序遍历数组中的位置

    以此可得到左子树和右子树的长度信息

    以此可确定左子树右子树在两个数组中的位置

  3. 递归建立左子树和右子树

递归的终止条件为“前序遍历数组为空”,此时返回空节点。

Tips: 可以在预处理时建立一个哈希表,以便能快速地找到根节点在中序遍历数组中的位置。

  • 时间复杂度 O ( N ) O(N) O(N),其中 N N N是节点个数
  • 空间复杂度 O ( N ) O(N) O(N)

AC代码

C++
class Solution {
private:
    unordered_map<int, vector<int>::iterator> ma;

    TreeNode* dfs(vector<int>::iterator preLeft, vector<int>::iterator preRight, vector<int>::iterator inLeft, vector<int>::iterator inRight) {
        if (preRight <= preLeft) {
            return nullptr;
        }
        TreeNode* thisNode = new TreeNode(*preLeft);
        vector<int>::iterator loc = ma[*preLeft];
        int leftLength = loc - inLeft;
        thisNode->left = dfs(preLeft + 1, preLeft + leftLength + 1, inLeft, loc);
        thisNode->right = dfs(preLeft + leftLength + 1, preRight, loc + 1, inRight);
        return thisNode;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for (vector<int>::iterator it = inorder.begin(); it != inorder.end(); it++) {
            ma[*it] = it;
        }
        return dfs(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
};
Python
from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:  # AC,98.61%,91.88%
    def dfs(self, preLeft: int, preRight: int, inLeft: int, inRight: int) -> Optional[TreeNode]:
        if preRight <= preLeft:
            return None
        thisNode = TreeNode(self.preorder[preLeft])
        loc = self.ma[self.preorder[preLeft]]
        leftLength = loc - inLeft
        thisNode.left = self.dfs(preLeft + 1, preLeft + leftLength + 1, inLeft, loc - 1)
        thisNode.right = self.dfs(preLeft + leftLength + 1, preRight, loc + 1, inRight)
        return thisNode
    
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        self.preorder = preorder
        self.inorder = inorder
        self.ma = dict()
        for i in range(len(inorder)):
            self.ma[inorder[i]] = i
        return self.dfs(0, len(preorder), 0, len(inorder))

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136186356

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

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

相关文章

小清新卡通人物404错误页面源码

小清新卡通人物404错误页面源码由HTMLCSSJS组成,记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c;重定向这个界面 蓝奏云&#xff1a;https://wfr.lanzout.com/i6XbU1olftde

区块链游戏解说:什么是 Nine Chronicles

作者&#xff1a;lesleyfootprint.network 编译&#xff1a;cicifootprint.network 数据源&#xff1a; Nine Chronicles Dashboard 什么是 Nine Chronicles Nine Chronicles 是一款去中心化的在线角色扮演游戏&#xff0c;标志着在线游戏和区块链技术的发展。 Nine Chroni…

ubuntu分辨率更改、开机被重置、ubuntu屏幕小

ubuntu分辨率更改 分辨率改成&#xff1a;1920x1200 xrandr --size 1920x1200 在此之前可以先输入 xrandr 看支持哪些分辨率 开机被重置 我已经设置成这样了&#xff0c; 一开机变回这个 ubuntu屏幕小 输入命令行 xrandr --size 1920x1200 这个下次重启ubuntu又会重置…

C++(18)——适配器概念以及stack、queue、优先队列的模拟实现

上篇文章中&#xff0c;给出了对于模拟实现中功能的补全&#xff0c;本篇文章将优先介绍一个新的容器之后引入什么是适配器&#xff0c;以及适配器的使用方法&#xff0c;再通过适配器的思想来完成对于&#xff0c;、优先级队列_的实现。 目录 1. deque: 1.1 什么是deque&…

ASP.NET-实现图形验证码

ASP.NET 实现图形验证码能够增强网站安全性&#xff0c;防止机器人攻击。通过生成随机验证码并将其绘制成图像&#xff0c;用户在输入验证码时增加了人机交互的难度。本文介绍了如何使用 C# 和 ASP.NET 创建一个简单而有效的图形验证码系统&#xff0c;包括生成随机验证码、绘制…

树莓派4B傻瓜式安装系统配置(无显示器)

一、前言&#xff1a; 本教程详细描述树莓派如何装系统&#xff0c;如何连接电脑显示屏&#xff0c;有详细安装包&#xff0c;有需要的可以点击链接下载&#xff0c;没有会员的宝宝可以关注后私信我。 &#xff08;树莓派4B傻瓜式安装系统配置&#xff08;无显示器&#xff0…

onlyoffice基础环境搭建+部署+demo可直接运行 最简单的入门

office这个体系分为四个大教程 1、【document server文档服务器基础搭建】 2、【连接器(connector)或者jsApi调用操作office】-进阶 3、【document builder文档构造器使用】-进阶 4、【Conversion API(文档转化服务)】-进阶 如果需要连接器&#xff0c;可以查看&#xff1a;onl…

Fiddler如何比较两个接口请求?

进行APP测试时&#xff0c;往往会出现Android和iOS端同一请求&#xff0c;但执行结果不同&#xff0c;这通常是接口请求内容差异所致。 我习惯于用Fiddler抓包&#xff0c;那此时应该如何定位问题呢&#xff1f; 分别把Android和iOS的接口请求另存为TXT文件&#xff0c;然后用…

leetcode hot100零钱兑换Ⅱ

本题可以看出也是背包问题&#xff0c;但区别于之前的01背包问题&#xff0c;这个是完全背包问题的变形形式。 下面介绍01背包和完全背包的区别与联系&#xff1a; 01背包是背包中的物品只能用一次&#xff0c;不可以重复使用&#xff0c;而完全背包则是可以重复使用。01/完全…

体验一下UE5.3的Skeletal Editor

UE5.3中增加了蒙皮网格骨架编辑工具&#xff0c;用户无需导出Fbx就可以直接编辑蒙皮网格&#xff0c;支持修改绑定姿势的骨骼位置、修改蒙皮权重、对已蒙皮多边形进行编辑以及对蒙皮网格减免等操作&#xff0c;就来体验一下。 1.加载插件 要使用Skeletal Editor功能&#xff…

使用系统调用实现shell命令之【ls -l】

时间获取: 1.time time_t time(time_t *tloc); 功能: 返回1970-1-1到现在的秒数&#xff08;格林威治时间&#xff09; 参数: tloc:存放秒数空间首地址 返回值: 成功返回秒数 失败返回-1 2.localtime stru…

Stable Diffusion——基础模型、VAE、LORA、Embedding各个模型的介绍与使用方法

前言 Stable Diffusion&#xff08;稳定扩散&#xff09;是一种生成模型&#xff0c;基于扩散过程来生成高质量的图像。它通过一个渐进过程&#xff0c;从一个简单的噪声开始&#xff0c;逐步转变成目标图像&#xff0c;生成高保真度的图像。这个模型的基础版本是基于扩散过程…

ESMFold conda安装、使用及与AlphaFold的简单比较

文章目录 前言一、ESMFold是什么&#xff1f;二、安装步骤1. 确认安装环境&#xff1a;cuda toolkit版本2. 创建ESMFold conda环境并安装Step 1&#xff1a;创建conda环境&#xff0c;下载需要的包Step 2&#xff1a;激活conda环境&#xff0c;继续pip安装 3. 运行结构预测 三、…

pom.xml常见依赖及其作用

1.org.mybatis.spring.boot下的mybatis-spring-boot-starter&#xff1a;这个依赖是mybatis和springboot的集成库&#xff0c;简化了springboot项目中使用mybatis进行持久化操作的配置和管理 2.org.projectlombok下的lombok&#xff1a;常用注解Data、NoArgsConstructor、AllA…

【Vuforia+Unity】AR02-长方体物体识别

1.创建模型 选择多维长方体图&#xff0c;这个长方体是生活中的真实物体的拍摄图&#xff0c;提前把6个面拍摄好并裁剪干净。 官网创建模型https://developer.vuforia.com/targetmanager/project/targets?projectId0ddbb5c17e7f4bf090834650bbea4995&avfalse 设置长宽高…

Rabbitmq入门与应用(六)-rabbitmq的消息确认机制

rabbitmq的消息确认机制 确认消息是否发送给交换机 配置 server:port: 11111 spring:rabbitmq:port: 5672host: 192.168.201.81username: adminpassword: 123publisher-confirm-type: correlated编码RabbitTemplate.ConfirmCallback ConfirmCallback 是一个回调接口&#xf…

突出最强算法模型——回归算法 !!

文章目录 1、特征工程的重要性 2、缺失值和异常值的处理 &#xff08;1&#xff09;处理缺失值 &#xff08;2&#xff09;处理异常值 3、回归模型的诊断 &#xff08;1&#xff09;残差分析 &#xff08;2&#xff09;检查回归假设 &#xff08;3&#xff09;Cooks 距离 4、学…

汽车电子论文学习---电动汽车用高功率密度碳化硅电机控制器研究

关键重点&#xff1a; sic的特点&#xff1a;耐压高、开关速度快、开关损耗小&#xff1b;采用sic的控制器&#xff0c;损耗降低70%&#xff0c;续航里程提高5%。sic的模块并联设计难度高于IGBT模块&#xff1b;多芯片并联导致热耦合问题、温升不均&#xff0c;导致部分芯片率…

合纵连横 – 以 Flink 和 Amazon MSK 构建 Amazon DocumentDB 之间的实时数据同步

在大数据时代&#xff0c;实时数据同步已经有很多地方应用&#xff0c;包括从在线数据库构建实时数据仓库&#xff0c;跨区域数据复制。行业落地场景众多&#xff0c;例如&#xff0c;电商 GMV 数据实时统计&#xff0c;用户行为分析&#xff0c;广告投放效果实时追踪&#xff…

【git】提交信息写错了,使用 amend 或者 reset 修改最近一次的提交信息 ,修改上上次/以前的提交信息

如果你的提交信息写错了&#xff0c;比如下面&#xff0c;你想修改【初始化项目】这5个字 修改最近一次的提交新的两个办法 &#xff08;1&#xff09;使用 reset 把这个提交重置&#xff0c;然后重新提交&#xff0c;reset 的使用方法请参考这篇文章。但是 reset 这种方法只能…