【面试经典150 | 二叉树】从中序与后序遍历序列构造二叉树

news/2024/2/22 19:09:10

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:递归
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【递归】【二叉树】


题目来源

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


题目解读

给你一棵二叉树的中序和后续遍历得到的两个数组,现在根据两个数组来构造二叉树。


解题思路

方法一:递归

前言

首先回忆一下二叉树的中序和后续遍历过程。

二叉树的中序遍历过程:

  • 先递归遍历左子树;
  • 接着遍历根节点;
  • 最后递归遍历右子树。

二叉树的后续遍历过程:

  • 先递归遍历左子树;
  • 接着递归遍历右子树;
  • 最后遍历根节点。

在「递归」遍历子树的过程中,我们也是将子树看成是一棵全新的树,按照相应的顺序进行遍历。

思路

根据后续遍历的顺序可知,后续遍历数组的最后一个元素为根节点。

于是可以根据后续遍历数组中的根节点定位到中序遍历中的根节点,接着可以将前序遍历数组分为左子树、根、右子树三部分,针对左子树和右子树这两个部分可以利用递归来完成二叉树的构造。

算法

我们需要查找后续遍历中的元素在中序遍历中的位置,为了高效查找,利用一个哈希表 idx_map 来记录中序遍历中元素的位置。

接着定义递归函数 helper(in_left, in_right) 表示在中序遍历的当前范围内(中序遍历的 [in_left, in_right])递归构造二叉树,递归入口为 helper(0, n - 1)

  • 递归出口:如果 in_left > in_right,说明子树为空,返回空节点;
  • 选择后续遍历的最后一个节点作为根节点;
  • 在哈希表 idx_map 中查询根节点在中序遍历中的 idx。从 in_leftidx - 1 数属于左子树,从 idx + 1in_right 属于右子树;
  • 根据后续遍历逻辑,递归创建右子树 helper(idx + 1, in_right) 和左子树 helper(in_left, idx - 1)
  • 最后返回根节点 root

注意:在递归创建子树的时候,先创建右子树,再创建左子树。因为在后续遍历中是先存储左子树的节点,再存储右子树的节点,最后存储根节点,如果每次选择「后续遍历的最后一个节点」为根节点,则先被构造出来的应该为右子树。

/*** 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 {
private:int root_idx;unordered_map<int, int> idx_map;
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {root_idx = postorder.size() - 1;// 建立哈希表int idx = 0;for (auto val : inorder) {idx_map[val] = idx++;}function<TreeNode*(int, int)> helper = [&](int in_left, int in_right) -> TreeNode* {if (in_left > in_right) {return nullptr;}// 选择 后续遍历数组的最后一个元素作为当前子树的根节点int root_val = postorder[root_idx--];TreeNode* root = new TreeNode(root_val);// 根据 root_val 所在位置分为左右两棵子树int idx = idx_map[root_val];// 递归构建右子树 root->right = helper(idx + 1, in_right);// 递归构建左子树root->left = helper(in_left, idx - 1);return root;};return helper(0, inorder.size() - 1);}
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为数中节点个数。

空间复杂度: O ( n ) O(n) O(n)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。


https://dhexx.cn/news/show-5177732.html

相关文章

国内大厂机器人赛道产品

大疆 大疆无人机自然不必说&#xff0c;除此之外大疆搞机甲大师&#xff0c;教育机器人。 字节 当前字节在机器人领域只是初步探索阶段&#xff0c;目前尚未发布相关产品&#xff08;截止至23.12&#xff09;。 管理层想法&#xff1a; 跟已有业务做结合&#xff0c;服务好…

rpc原理与应用

IPC和RPC&#xff1f; RPC 而RPC&#xff08;Remote Procedure Call&#xff09;&#xff0c;又叫做远程过程调用。它本身并不是一个具体的协议&#xff0c;而是一种调用方式。 gRPC 是 Google 最近公布的开源软件&#xff0c;基于最新的 HTTP2.0 协议&#xff0c;并支持常见…

【解密考研英语:Python数据分析与可视化】

解密考研英语&#xff1a;Python数据分析与可视化 背景数据集技术选型功能实现创新点 大家好&#xff0c;欢迎阅读我的CSDN博客&#xff01;今天我将分享一项有关考研英语真题的数据分析与可视化项目&#xff0c;希望对考研学子提供更有针对性的复习帮助。 背景 作为考研学子…

元素定位,年轻人在 Web UI 自动化成长道路上吃的第一个亏

01/Katalon Studio 的 Web spy spy 英文翻译过来的意思是&#xff1a;间谍、密探。是具有监视意识的。 所以我们可以使用这个功能去监视 Web 元素并定位出来。具体操作如下&#xff1a;1&#xff0c;打开 Katalon 并创建好项目工程 2&#xff0c;在快捷键栏里点击 Web spy 如…

Java面试遇到的一些常见题

目录 1. Java语言有几种基本类型&#xff0c;分别是什么&#xff1f; 整数类型&#xff08;Integer Types&#xff09;&#xff1a; 浮点类型&#xff08;Floating-Point Types&#xff09;&#xff1a; 字符类型&#xff08;Character Type&#xff09;&#xff1a; 布尔类…

【Linux】:线程(二)互斥

互斥与同步 一.线程的局部存储二.线程的分离三.互斥1.一些概念2.上锁3.锁的原理4.死锁 一.线程的局部存储 例子 可以看到全局变量是所有线程共享的&#xff0c;如果我们想要每个线程都单独访问g_val怎么办呢&#xff1f;其实我们可以在它前面加上__thread修饰。 这就相当于把g…

重心坐标:定义、公式与应用

重心坐标&#xff08;Barycentric Coordinates&#xff09;在 CG 中尤为重要。 它们有一些功能&#xff0c;是 Mller-Trumbore 提出的下一个射线三角形相交算法的关键&#xff0c;该算法将在下一章中研究。 本章最后将讨论如何在 CG 中使用重心坐标。 NSDT工具推荐&#xff1a;…

[陇剑杯 2021]简单日志分析

[陇剑杯 2021]简单日志分析 题目做法及思路解析&#xff08;个人分享&#xff09; 问一&#xff1a;某应用程序被攻击&#xff0c;请分析日志后作答&#xff1a; 黑客攻击的参数是______。&#xff08;如有字母请全部使用小写&#xff09;。 题目思路&#xff1a; 分析…

pytest +uiautomator2+weditor app自动化从零开始

目录结构1.0 把设备连接单独移出去了 模块操作代码&#xff0c;有一些流程操作和断言方法 from devices import dv from time import sleep import random from tool.jt import capture_screenshotdef initialization(func):def wrapper():sleep(1)dv.app_stop(com.visteon.…

【STM32】TIM定时器编码器

1 编码器接口简介 Encoder Interface 编码器接口 编码器接口可接收增量&#xff08;正交&#xff09;编码器的信号&#xff0c;根据编码器旋转产生的正交信号脉冲&#xff0c;自动控制CNT自增或自减&#xff0c;从而指示编码器的位置、旋转方向和旋转速度 接收正交信号&#…