【算法】递归+深搜+哈希表:889.根据前序和后序遍历构造二叉树

目录

1、题目链接

相似题目:

2、题目

​3、解法(针对无重复值,哈希表+递归)

函数头-----找出重复子问题

函数体---解决子问题

4、代码


1、题目链接

889.根据前序和后序遍历构造二叉树(LeetCode)

相似题目:

105.从前序与中序遍历序列构造二叉树(LeetCode)

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


2、题目


3、解法(针对无重复值,哈希表+递归)

前序:根节点、左子树、右子树
后序:左子树、右子树、根节点

二叉树的根节点一定是前序遍历的第一个节点,也是后序遍历的最后一个节点。

接下来,我们需要确定二叉树的左子树范围和右子树范围。

        首先,仅凭前序和后序,得不到唯一的二叉树。结果可能有多个。
        没有中序遍历的情况下,无法区分哪些节点属于左子树,哪些属于右子树。
        第二个元素我们默认他是左子树的根节点。

函数头-----找出重复子问题

深搜函数头:preorder前序数组,

                        root :根节点在前序的下标

                        left:根节点所在子树的左边界

                        right:根节点所在子树的右边界

TreeNode* dfs(const vector<int>& preorder, int root, int left, int right)

函数体---解决子问题

哈希表 hash,它存储了后序遍历中每个节点的位置。在函数的开头,我们可以找到任意节点在后序遍历中的位置。

  1. 如果 left >right ,说明范围为空,直接返回空节点。
  2. 否则,我们构造一个新的节点 node ,它的值为前序遍历中的第一个节点的值,也就是 preorder[root]。
  3. 如果 left 等于 right ,说明 root 没有左子树也没有右子树,直接返回 root。
  4. 否则,左子树的根节点的值为 preorder[ root + 1],我们在后序遍历中找到 preorder[ root + 1] 的位置,记为 pos_root。
    1. 那么左子树的节点个数 left_size = pos_root − left + 1,由此可知左子树后序遍历中的范围是 [left , pos_root ],右子树在后序遍历中的范围是 [pos_root + 1, right −1]。
  5. 知道了左右子树的范围,我们就可以递归地重建左右子树,然后将左右子树的根节点分别作为 node 的左右子节点。最后返回 node。

        if (left > right)
            return NULL;

        TreeNode* node = new TreeNode(preorder[root]);//构建根节点
       
        //非常重要!!!影响整个代码的通过
        //root 没有左子树也没有右子树,直接返回 root。
        if (left == right)
            return node;

        int pos_root = hash[preorder[root + 1]];    //左子树的root在后序的下标
        
        int left_size = pos_root - left + 1; //左子树结点数(含root)
        int right_root = root + left_size + 1;//右子树根节点在前序中的下标

        node->left = dfs(preorder, root+1, left, pos_root);
        node->right = dfs(preorder, right_root, pos_root + 1, right - 1);


4、代码

class Solution {

    //仅仅依靠前序、后序,会有存在多个二叉树
public:
    unordered_map<int, int> hash;

    //root 在pre的下标
    TreeNode* dfs(const vector<int>& preorder, int root, int left, int right)
    {
        if (left > right)
            return NULL;

        TreeNode* node = new TreeNode(preorder[root]);//构建根节点
       
        //非常重要!!!影响整个代码的通过
        //root 没有左子树也没有右子树,直接返回 root。
        if (left == right)
            return node;

        int pos_root = hash[preorder[root + 1]];    //左子树的root在后序的下标
        
        int left_size = pos_root - left + 1; //左子树结点数(含root)
        int right_root = root + left_size + 1;//右子树根节点在前序中的下标

        node->left = dfs(preorder, root+1, left, pos_root);
        node->right = dfs(preorder, right_root, pos_root + 1, right - 1);

        return node;
    }

    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        //postorder填充hash
        for (int i = 0; i < postorder.size(); i++)
        {
            hash[postorder[i]] = i;
        }

        return dfs(preorder, 0, 0, postorder.size() - 1);
    }
};

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

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

相关文章

基于SpringBoot的“乐校园二手书交易管理系统”的设计与实现(源码+数据库+文档+PPT)

基于SpringBoot的“乐校园二手书交易管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统首页界面图 用户注册界面图 二手…

“高效开发之路:用Spring MVC构建健壮的企业级应用”

一、SpringMVC框架概念&#xff1a; &#xff08;一&#xff09;概述 SpringMVC是Spring框架的一个模块&#xff0c;Spring和SpringMVC无需中间整合层整合。该模块是一个基于MVC的web框架。 作用&#xff1a;只要需要前后端通信&#xff0c;就需要springMVC帮我完成&#xff…

练习LabVIEW第四十一题

学习目标&#xff1a; 编写一个程序测试自己在程序前面板上输入一段文字“CSDN是一个优秀的网站”所用的时间。 开始编写&#xff1a; 前面板放置一个数值显示控件&#xff0c;程序框图添加顺序结构共三帧&#xff0c;第一帧放一个获取日期/时间&#xff08;秒&#xff09;函…

编程之路:蓝桥杯备赛指南

文章目录 一、蓝桥杯的起源与发展二、比赛的目的与意义三、比赛内容与形式四、比赛前的准备五、获奖与激励六、蓝桥杯的影响力七、蓝桥杯比赛注意事项详解使用Dev-C的注意事项 一、蓝桥杯的起源与发展 蓝桥杯全国软件和信息技术专业人才大赛&#xff0c;简称蓝桥杯&#xff0c…

Cofounder:全栈 AI 应用开发 Agent,基于单一提示生成完整的应用程序

❤️ 如果你也关注大模型与 AI 的发展现状&#xff0c;且对大模型应用开发非常感兴趣&#xff0c;我会快速跟你分享最新的感兴趣的 AI 应用和热点信息&#xff0c;也会不定期分享自己的想法和开源实例&#xff0c;欢迎关注我哦&#xff01; &#x1f966; 微信公众号&#xff…

神奇!KMeans也可以进行图像语义分割?基于k-Means的遥感图像语义分割实战

《------往期经典推荐------》 一、AI应用软件开发实战专栏【链接】 项目名称项目名称1.【人脸识别与管理系统开发】2.【车牌识别与自动收费管理系统开发】3.【手势识别系统开发】4.【人脸面部活体检测系统开发】5.【图片风格快速迁移软件开发】6.【人脸表表情识别系统】7.【…

2.2、软件生命周期模型介绍

软件生命周期模型 1. 传统软件过程模型1.1 瀑布模型Waterfall model1.2 V模型1.3 原型模型&#xff08;降低需求不明确的风险&#xff09;1.4 增量模型&#xff08;降低需求变化风险&#xff09;1.5 螺旋模型1.6 喷泉模型 2. 现代模型2.1 基于构件的开发模型2.2 统一过程RUP:Ra…

推荐程序员好用的浏览器插件

推荐程序员好用的浏览器插件 1. 网页颜色控制&#xff1a;Dark Reader安装效果 2. 前端助手&#xff1a;FeHelper安装效果 3. markdown可视化&#xff1a;Markdown Reader安装效果 4. ES插件&#xff1a;Multi Elasticsearch Heads安装效果 1. 网页颜色控制&#xff1a;Dark Re…

使用Jest进行JavaScript单元测试

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用Jest进行JavaScript单元测试 引言 Jest 简介 安装 Jest 创建基本配置 编写测试用例 运行测试 快照测试 模拟函数 代码覆盖率…

白杨SEO:百度在降低个人备案类网站搜索关键词排名和流量?怎样应对?【参考】

很久没有写百度或者网站这块内容了&#xff0c;一是因为做百度网站朋友越来越少&#xff0c;不管是个人还是企业&#xff1b;二是百度上用户搜索与百度给到网站的流量都越来越少。 为什么想到今天又来写这个呢&#xff1f;因为上个月有个朋友来咨询我说网站百度排名全没了&…

Linux——Shell的运行原理和Linux文件权限

Shell的运行原理和Linux文件权限 文章目录 Shell的运行原理和Linux文件权限1. Shell的运行原理(1) Shell是什么(2) 为什么要有Shell(3) Shell的运行原理(4) 解析命令行 2. Linux文件(1) 文件属性(2) 文件类型(3) 文件权限(4) 文件权限的修改(1) chmod(2) chown(3) chgrp (5) um…

linux守护进程与后台进程的区别

守护进程与后台进程有以下区别&#xff1a; 1. 概念与定义 后台进程&#xff1a; 是指在操作系统后台运行的进程&#xff0c;它不与用户直接交互&#xff08;没有连接到用户的终端&#xff09;。用户在终端中启动一个程序并让其在后台运行&#xff08;如通过在命令后加“&…

Jmeter5.X性能测试

Jmeter5.X性能测试 文章目录 Jmeter5.X性能测试一、掌握Http基础协议1.1 浏览器的B/S架构和C/S架构1.2 HyperText Transfer Protocol 超文本传输协议1.3 超文本传输协议Http消息体拆分讲解1.4 HTTP的九种请求方法和响应码介绍1.5 Http请求头/响应头1.6 Http常见请求/响应头cont…

Spring 配置绑定原理分析

Spring 配置绑定原理分析 前言 Spring 应用中存在诸多配置&#xff0c;有的是系统配置&#xff0c;有的命令行启动参数配置&#xff0c;有的是yaml配置&#xff0c;有的是分布式配置中心配置&#xff0c;但对使用者而言总是可以通过ConfigurationProperties将它关联到一个Java…

爬虫下载网页文夹

爬虫下载网页pdf文件 import os import requests from bs4 import BeautifulSoup from urllib.parse import urljoin from urllib.parse import urljoin, unquote from tqdm import tqdm # 设置网页的URL base_url "http://119/download/dzz/pdf/"# 创建保存文件的…

数据结构-归并排序笔记

【数据结构】八大排序(超详解附动图源码)_数据结构排序-CSDN博客 看这个学思路 一 归并排序介绍: 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法&#xff0c;该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解&#xf…

编译器优化乌龙——记一次死循环不进入问题

记一次死循环不生效问题 看如下代码&#xff0c;本意是我们模拟一次死循环&#xff0c;然后会在中断处理函数中更改waiting的值&#xff0c;更改waiting的值后&#xff0c;跳出死循环。 int waiting 0; while(waiting0){}运行起来发现&#xff0c;程序根本就没有进入这个死循…

构建第一个ArkTs应用

1、新建第一个页面文件。在“Project”窗口&#xff0c;点击“entry > src > main > ets > pages”&#xff0c;打开“Index.ets”文件&#xff0c;进行页面的编写。 2、新建第二个页面文件。在“Project”窗口&#xff0c;打开“entry > src > main > e…

一文搞懂Linux kernel编译步骤

一、前言 什么是Linux的内核编译呢&#xff1f;简单来说&#xff0c;Linux内核编译是一个将内核源代码转换成可在特定的硬件架构上运行的二进制文件的过程。通过编译内核&#xff0c;我们可以根据自己的需求和兴趣对内核进行定制和优化&#xff0c;以满足特定的应用场景。下文…

IDEA构建JavaWeb项目,并通过Tomcat成功运行

目录 一、Tomcat简介 二、Tomcat安装步骤 1.选择分支下载 2.点击下载zip安装包 3.解压到没有中文、空格和特殊字符的目录下 4.双击bin目录下的startup.bat脚本启动Tomcat 5.浏览器访问Tomcat 6.关闭Tomcat服务器 三、Tomcat目录介绍 四、WEB项目的标准结构 五、WEB…