首页/新闻资讯/正文详情

DeepSeek LeetCode 105. 从前序与中序遍历序列构造二叉树 C语言实现

发布时间:2026/9/25 20:26:26 来源:云帆数科 栏目:资讯中心
DeepSeek    LeetCode 105. 从前序与中序遍历序列构造二叉树 C语言实现
思路前序遍历顺序[根, 左子树…, 右子树…]第一个元素一定是根。中序遍历顺序[左子树…, 根, 右子树…]根将中序序列分为左右两部分。递归构造从前序取第一个元素作为根。在中序中找到根的位置 mid则左子树节点数为 mid - inL。根据左子树节点数切分前序区间递归构造左右子树。为了快速定位根在中序中的位置使用数组映射因为题目节点值范围是 -3000 到 3000实现 O(1) 查找。整体时间复杂度 O(n)。代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */// 辅助递归函数structTreeNode*build(intpreL,intpreR,intinL,intinR,int*preorder,int*inorder,int*indexMap){if(preLpreR){returnNULL;}introotValpreorder[preL];structTreeNode*root(structTreeNode*)malloc(sizeof(structTreeNode));root-valrootVal;root-leftNULL;root-rightNULL;// 根在中序中的位置intmidindexMap[rootVal3000];intleftSizemid-inL;// 递归构造左右子树root-leftbuild(preL1,preLleftSize,inL,mid-1,preorder,inorder,indexMap);root-rightbuild(preLleftSize1,preR,mid1,inR,preorder,inorder,indexMap);returnroot;}structTreeNode*buildTree(int*preorder,intpreorderSize,int*inorder,intinorderSize){// 建立中序索引映射值范围 [-3000, 3000]intindexMap[6001];for(inti0;i6001;i){indexMap[i]-1;}for(inti0;iinorderSize;i){indexMap[inorder[i]3000]i;}returnbuild(0,preorderSize-1,0,inorderSize-1,preorder,inorder,indexMap);}关键点数组映射加速查找节点值范围固定用 val 3000 作为下标数组大小 6001。区间为闭区间前序 [preL, preR]中序 [inL, inR]终止条件 preL preR。左子树节点数leftSize mid - inL。前序区间划分· 左子树[preL 1, preL leftSize]· 右子树[preL leftSize 1, preR]中序区间划分· 左子树[inL, mid - 1]· 右子树[mid 1, inR]内存分配每个节点 mallocLeetCode 不要求释放。示例走一遍preorder [3,9,20,15,7]inorder [9,3,15,20,7]· 根 3mid 1leftSize 1· 左子树前序 [9]中序 [9] → 节点 9· 右子树前序 [20,15,7]中序 [15,20,7]· 根 20mid 1leftSize 1· 左子树前序 [15]中序 [15] → 节点 15· 右子树前序 [7]中序 [7] → 节点 7得到3 / \ 9 20 / \ 15 7复杂度· 时间复杂度O(n)每个节点访问一次映射查找 O(1)。· 空间复杂度O(n)递归栈最坏 O(n)映射数组 O(1)固定 6001。易错点· 忘记初始化 indexMap 为 -1导致未映射的值被误用。· 偏移量写错如写成 3001 或数组大小不足。· 区间边界计算错误尤其是 leftSize 和前序右子树起点。· 如果节点值范围超出 [-3000, 3000]此方法会越界。此时应改用哈希表或二分查找。· C 语言中不能嵌套定义函数辅助函数需定义在外部并将 indexMap 作为参数传递。· 空树情况若 preorderSize 0直接返回 NULL本代码递归中已处理。

相关推荐

量子仿真如何实现健康轨迹实时动态预测
量子仿真如何实现健康轨迹实时动态预测

随着精准医疗、智慧健康产业的快速迭代,人体健康管理已从传统的静态体检、事后诊疗模式,转向动态监测、提前预判、主动干预的全周期健康管控模式。人体是典型的高维、非线性、强耦合的复杂生命系统,基因序列、代谢水平、脏器功能、生活作息、… · 2026/9/25 20:26:20

Atlas 300V 24G部署YOLO全攻略:从推理加速卡认知到OM转换与AscendCL实战
Atlas 300V 24G部署YOLO全攻略:从推理加速卡认知到OM转换与AscendCL实战

你在热搜里同时看到“atlas部署yolo”和“atlas 300v 24g 是运算加速卡吗”这两句话时,基本可以判断提问者正处于同一个阶段:手里刚拿到一张Atlas 300V 24G,第一个念头不是赶紧跑模型,而是反复确认手里的东西到底是什么。这个疑问… · 2026/9/25 20:26:20

MicYou插件系统全景解析:Native与WASM双运行时架构是如何设计的
MicYou插件系统全景解析:Native与WASM双运行时架构是如何设计的

MicYou插件系统全景解析:Native与WASM双运行时架构是如何设计的 【免费下载链接】MicYou MicYou is a powerful tool that turns your Android device into a high-quality microphone for your PC. 项目地址: https://gitcode.com/gh_mirrors/mi/MicYou MicYou 是一款将… · 2026/9/25 20:25:48

MindSpeed LLM通信计算重叠与MC2:如何榨干昇腾芯片算力
MindSpeed LLM通信计算重叠与MC2:如何榨干昇腾芯片算力

MindSpeed LLM通信计算重叠与MC2:如何榨干昇腾芯片算力 【免费下载链接】MindSpeed-LLM 昇腾LLM分布式训练框架 项目地址: https://gitcode.com/Ascend/MindSpeed-LLM MindSpeed-LLM 是昇腾(Ascend)平台上的 LLM 分布式训练框架&#… · 2026/9/25 20:52:44

AI Agent 为什么总是忘事?我用 Graphiti 给它装了一个会记时间的知识图谱大脑
AI Agent 为什么总是忘事?我用 Graphiti 给它装了一个会记时间的知识图谱大脑

我们现在做 AI Agent,经常会遇到一个很尴尬的问题: 模型明明很聪明,但就是记不住事。 比如你跟一个 AI 助手聊了半年。 三月份你告诉它:我现在主要写 Java。五月份你又说:最近项目全部转 Go 了。到了九月份&#xff0c… · 2026/9/25 20:52:25

车型识别不准,一年多赔多少钱?
车型识别不准,一年多赔多少钱?

如果你管着一家保险机构、融资租赁公司或者车队,这笔账值得算一算:车型识别偏差,一年到底吃掉多少成本?先看保险侧。车型决定了基准保费和赔付基准,车型定错,费率就套错了。把高配车按低配投保,… · 2026/9/25 20:52:13

2026-09-24:统计范围内的好整数。用go语言,有三个整数 l、r、k。 对于一个整数,把它写成十进制形式后,如果任意两个挨着的数字之间的差的绝对值都不超过 k,就认为这个整数满足条件。
2026-09-24:统计范围内的好整数。用go语言,有三个整数 l、r、k。 对于一个整数,把它写成十进制形式后,如果任意两个挨着的数字之间的差的绝对值都不超过 k,就认为这个整数满足条件。

2026-09-24:统计范围内的好整数。用go语言,有三个整数 l、r、k。 对于一个整数,把它写成十进制形式后,如果任意两个挨着的数字之间的差的绝对值都不超过 k,就认为这个整数满足条件。 现在需要统计从 l 到 r 这个闭区间… · 2026/9/25 20:51:47

yichen-skills 开发者指南:从 SKILL.md 到脚本,自建一个 AI Agent 技能全流程
yichen-skills 开发者指南:从 SKILL.md 到脚本,自建一个 AI Agent 技能全流程

yichen-skills 开发者指南:从 SKILL.md 到脚本,自建一个 AI Agent 技能全流程 【免费下载链接】yichen-skills 项目地址: https://gitcode.com/gh_mirrors/yi/yichen-skills yichen-skills 是一个面向内容创作者的开源 AI Agent 技能仓库&#x… · 2026/9/25 20:51:47

Atlas 300V推理加速卡上的YOLO部署实践:从模型转换到性能调优
Atlas 300V推理加速卡上的YOLO部署实践:从模型转换到性能调优

Atlas 上的 YOLO 部署指南:从硬件认知到推理落地最近后台一直有朋友在问 Atlas 300V 24G 到底是不是运算加速卡,又要怎么在它上面跑 YOLO。这批问题特别集中,今天干脆把这块卡和整套部署流程一次说清楚。Atlas 300V 24G 是运算加速卡&#xf… · 2026/9/25 20:51:21

数值优化(Numerical Optimization)学习系列-03-共轭梯度方法(Conjugate Gradient)
数值优化(Numerical Optimization)学习系列-03-共轭梯度方法(Conjugate Gradient)

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/25 1:00:31

创维E900V22D刷机全攻略:S905L3SB芯片兼容性解析与救砖实战
创维E900V22D刷机全攻略:S905L3SB芯片兼容性解析与救砖实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/25 1:00:31

MQTT协议原理与Broker服务器搭建实战:从Mosquitto到EMQX
MQTT协议原理与Broker服务器搭建实战:从Mosquitto到EMQX

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/25 1:00:37

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码