106.从中序与后序遍历序列构造二叉树-北京尧图网络

题目编号: 106题目名称: 106.从中序与后序遍历序列构造二叉树难度: 中等题目信息链接从中序与后序遍历序列构造二叉树考察知识点二叉树、递归、迭代解题思路解法一递归使用哈希表存储inorder中对应元素的下标降低查找时间然后递归使用根节点索引建立右子树和左子树。代码如下classSolution{privateint[]postorder;privateMapInteger,IntegerinorderMapnewHashMap();privateintpostIdx;publicTreeNodebuildTree(int[]inorder,int[]postorder){this.postorderpostorder;this.postIdxpostorder.length-1;for(inti0;iinorder.length;i){inorderMap.put(inorder[i],i);}returnbuild(0,inorder.length-1);}privateTreeNodebuild(intinLeft,intinRight){if(inLeftinRight)returnnull;introotValpostorder[postIdx--];TreeNoderootnewTreeNode(rootVal);intinRootinorderMap.get(rootVal);root.rightbuild(inRoot1,inRight);root.leftbuild(inLeft,inRoot-1);returnroot;}}复杂度分析时间复杂度O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)。解法二简单来说每次从后序里拿一个新节点它要么是栈顶的右孩子要么是某个祖先包括自己的左孩子。光看后序根本分不清所以我们自然想到用中序来帮忙 ——中序里一个节点出现了就说明它的右子树已经全部走完了。有了这个判断依据事情就简单了如果栈顶在中序里还没出现说明它的右路还没走完新节点直接挂成它的右孩子。如果栈顶已经在中序里出现了说明它和它上面的父亲、爷爷可能都完工了。那就顺着栈往上弹像认亲一样逐个问“你的右子树走完了吗”直到碰见第一个回答“没走完”的祖先为止。这时候停下来新节点就挂在刚刚被弹出去的那个节点也就是这个祖先的右孩子的左边。代码如下classSolution{publicTreeNodebuildTree(int[]inorder,int[]postorder){if(postordernull||postorder.length0){returnnull;}DequeTreeNodestacknewArrayDeque();intindexinorder.length-1;introotValpostorder[postorder.length-1];TreeNoderootnewTreeNode(rootVal);stack.push(root);for(intipostorder.length-2;i0;i--){// 从后序遍历序列中把结点值拿出来intvalpostorder[i];// 判断当前栈顶是不是右子树构建完了TreeNodenodestack.peek();// 右子树还没构建完应该挂在栈顶if(node.val!inorder[index]){node.rightnewTreeNode(val);stack.push(node.right);}else{// 弹出栈顶的结点直到栈为空或者遇到第一个右子树没有构建完的结点while(!stack.isEmpty()stack.peek().valinorder[index]){//保存每次弹出的结点nodestack.pop();// 中序遍历递减index--;}//从循环出来意味着当前栈顶元素的右子树没有构建完//应该把这个新结点挂在上一轮弹出的结点左边node.leftnewTreeNode(val);//然后把这个结点压入stack.push(node.left);}}returnroot;}}复杂度分析时间复杂度O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)。

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

相关推荐

Django 权限系统项目实战详细图文教程1--前后端架构搭建设计

容器虚拟化基础--NameSpace空间隔离详解

Java多线程八股文：核心知识点与高频面试题解析

更多资讯

VS Code高效开发指南：工作区、多光标与调试技巧

统信UOS服务器部署OpenClaw AI Agent完整避坑手册

Kubernetes生产实战：HPA自动扩缩容与Helm编排实践

HPA与Helm实战：Kubernetes自动扩缩容与模板化部署

单周期RISC-V CPU设计：Vivado实战与FPGA落地指南

用GDAL实现遥感影像裁剪：从范围裁剪到批量处理实战

今日更新

微信云开发旅游小程序实战：LBS打卡+UGC社交全栈方案

金融AI代理平台核心拆解：从多代理协作到财报分析实战

基于大数据的智慧旅游推荐与可视化平台架构实践

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？