【leetcode面试经典150题】73. 从中序与后序遍历序列构造二叉树(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)

【题目描述】

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

【示例一】

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

【示例二】

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

【提示及数据范围】

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

【代码】

// 方法一:递归

class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了,就结束
        if (in_left > in_right) {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立(元素,下标)键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};

// 方法二:迭代

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) {
            return nullptr;
        }
        auto root = new TreeNode(postorder[postorder.size() - 1]);
        auto s = stack<TreeNode*>();
        s.push(root);
        int inorderIndex = inorder.size() - 1;
        for (int i = int(postorder.size()) - 2; i >= 0; i--) {
            int postorderVal = postorder[i];
            auto node = s.top();
            if (node->val != inorder[inorderIndex]) {
                node->right = new TreeNode(postorderVal);
                s.push(node->right);
            } else {
                while (!s.empty() && s.top()->val == inorder[inorderIndex]) {
                    node = s.top();
                    s.pop();
                    inorderIndex--;
                }
                node->left = new TreeNode(postorderVal);
                s.push(node->left);
            }
        }
        return root;
    }
};

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

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

相关文章

BUUCTF-MISC-09文件中的秘密1

9.文件中的秘密1 题目&#xff1a;flag包含在图片的属性中

CentOS 7.9.2009 中 Docker 使用 GPU

一、安装nvidia驱动 1.1&#xff0c;查看显卡驱动 # 查看显卡型号 lspci | grep -i nvidia 1.2&#xff0c;进入 PCI devices &#xff0c;输入上一步查询到的 2204 1.3&#xff0c;进入 官方驱动 | NVIDIA&#xff0c;查询 Geforce RTX 3090 驱动并下载 1.4&#xff0c;禁用…

【java、微服务】MQ

MQ(MessageQueue)&#xff0c;中文是消息队列&#xff0c;字面来看就是存放消息的队列。也就是事件驱动架构中的Broker。 同步通讯 优点 时效性较强&#xff0c;可以立即得到结果 问题 微服务间基于Feign的调用就属于同步方式&#xff0c;存在一些问题。 耦合度高。每次加…

无人机干扰技术及干扰设备突破性发展

无人机干扰技术主要指的是通过各种手段干扰无人机的正常运行&#xff0c;从而达到使其失去控制、降低其性能或获取其信息的目的。这些干扰手段可以包括无线电干扰、GPS干扰、信号屏蔽、光学干扰等。 1.无线电干扰&#xff1a;由于无人机在遥控、定位、数据传输等方面都依赖于无…

云服务器搭建XSS-platform、DVWA靶机和Permeate论坛

目录 前言准备环境安装步骤一、 部署MySQL二、 系统部署三、系统安装主页介绍 前言 我发现目前网上的xss-platform的搭建教程都是基于本地搭建的&#xff0c;这样搭建好的xss平台只能在本地使用&#xff0c;无法测试别的网站。而网络上的大部分xss平台又几乎都是收费的&#x…

三维图形程序员入门-openmesh

三维网格入门第一篇&#xff0c;学习使用openmesh&#xff0c;三维模型的读取、存储有自己的数据结构&#xff0c;要想详细了解就开始学习openmesh&#xff0c;openmesh是开源的一个三角网格处理库&#xff0c;有三维顶点、面片、边、半边等&#xff0c;还有遍历算法、法向求解…

常见大厂面试题(SQL)02

小鹏面试题: 小鹏汽车充电每辆车连续快充最大次数 原表charging_data idcharge_timecharge_typeXP10012023/11/20 8:45快充XP10012023/11/21 20:45快充XP10012023/11/22 8:45快充XP10012023/11/23 8:45慢充XP10012023/11/25 8:45快充XP10022023/11/25 8:45快充XP10022023/11/…

Orange3数据可视化组件概览

概要 大家见过Orange3提供的丰富数据可视化组件吗&#xff1f; Orange3为您提供了一系列生动的图表工具&#xff0c;包括树图、箱线图、小提琴图、分布图、散点图、折线图、条形图、筛图、马赛克图、自由投影、线性投影、雷达图、热力图、韦恩图、轮廓图、毕达哥拉斯树、毕达哥…

C++_第八周做题总结

id:45 A.Equation(类与对象构造) 题目描述 建立一个类Equation&#xff0c;表达方程ax2bxc0。类中至少包含以下方法&#xff1a; 无参构造&#xff08;abc默认值为1.0、1.0、0&#xff09;与有参构造函数&#xff0c;用于初始化a、b、c的值&#xff1b; set方法&#xff0c;…

【AI学习】Transformer的Token嵌入表示为什么那么长

有朋友问&#xff0c;BERT等大模型的参数量怎么计算的&#xff1f;这个问题&#xff0c;李沐在BERT那篇论文中讲过&#xff0c;主要包括几部分。1、词嵌入&#xff1a;token数量乘以token表示的向量长度&#xff0c;就是 VH&#xff1b;2、注意力计算没有参数&#xff0c;只计算…

MT2041 三角形的个数

思路&#xff1a;找规律&#xff0c;推公式 4等分&#xff1a; 头朝上的三角形&#xff1a; 边长为1&#xff1a;1234s1&#xff1b; 边长为2&#xff1a;123s2&#xff1b; 边长为3&#xff1a;12s3&#xff1b; 边长为4&#xff1a;1s4&#xff1b; 即si12...n-i1(n-i2)*(n-i…

STM32玩转物联网实战篇:5.ESP8266 WIFI模块MQTT通信示例详解

1、准备开发板 开发板功能区分布图 开发板俯视图 2、实验讲解 在之前的章节中&#xff0c;已经讲解过了MQTT的通讯原理和组包过程&#xff0c;现在开始手把手的教大家用代码来实现连接MQTT平台以及数据的交互&#xff0c;实际上这篇文章已经拖更接近两年了&#xff0c;非常…

VS2019中配置C++ OpenCV 4.5.4完整指南

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的在读研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三…

基于STM32的报警器

参考前面的内容&#xff1a;STM32点灯大师&#xff08;中断法&#xff09;-CSDN博客 同样是使用中断的方式触发警报 一、GPIO口配置起来 二、代码 打开gpio.c 重写虚函数&#xff0c;实现我们想要的功能 -----------------------------------------------------------------…

变频器基础原理

文章目录 0. 基本知识1.三相的电压之和为02.正弦交流相量的相量表示法(相量只是表示正弦量&#xff0c;而不等于正弦量 &#xff1b;只有正弦量才能用相量表示)引入相量表示法目的:一种正弦量的产生方式:正弦量的相量表示&#xff0c;使用欧拉公式表示复数 3.用复数表示正弦量&…

Redis入门到通关之Redis网络模型-用户空间和内核态空间

文章目录 欢迎来到 请回答1024 的博客 &#x1f353;&#x1f353;&#x1f353;欢迎来到 请回答1024的博客 关于博主&#xff1a; 我是 请回答1024&#xff0c;一个追求数学与计算的边界、时间与空间的平衡&#xff0c;0与1的延伸的后端开发者。 博客特色&#xff1a; 在我的…

25考研数学可以全程跟张宇吗?

先说结论&#xff1a;25可以全程跟张宇。除了这三种情况。 总的来说&#xff0c;张宇的知识点是全的&#xff0c;不需要担心漏知识点、漏经典方法。不单高数&#xff0c;线代概率也是这样。 但是&#xff0c;老师讲得好&#xff0c;不能保证你上岸。 如果遇到这三种情况&…

java银行存取款程序设计

银行存取款的流程是人们非常熟悉的事情&#xff0c;用户可在银行对自己的资金账户进行存款、取款、查询余额等操作&#xff0c;极大的便利了人民群众对资金的管理。 本任务要求&#xff0c;使用所学知识编写一个银行存取款程序&#xff0c;实现存取款功能。编写一个帐户类实现…

LeetCode //C - 38. Count and Say Medium Topics Companies

38. Count and Say The count-and-say sequence is a sequence of digit strings defined by the recursive formula: countAndSay(1) “1”countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a differen…

StrongSORT——基于DeepSORT,提高多目标跟踪的准确性和鲁棒性

1、概述 1.1 DeepSORT DeepSORT算法是在SORT基础上发展起来的一种多目标跟踪算法。SORT算法结合了目标检测器和跟踪器&#xff0c;其中跟踪器的核心是卡尔曼滤波和匈牙利算法。 卡尔曼滤波用于预测目标在下一帧的位置和状态而匈牙利算法则用于将预测状态与实际检测结果进行最…