【算法四】从前序和中序遍历构造二叉树-云帆数科

一、为什么必须传两个数组很多初学者第一反应是为什么不能只给一个遍历结果就把树还原出来因为单独一个遍历信息不够前序遍历根 - 左子树 - 右子树能立刻知道“谁是根”但看不出左子树和右子树的边界在哪里。中序遍历左子树 - 根 - 右子树能看出根的左边全是左子树、右边全是右子树但看不出整棵树最顶层的根是谁以及递归时谁先谁后。两个配合就刚好前序负责找根中序负责切左右。例子preorder[3,9,20,15,7]inorder[9,3,15,20,7]前序第一个是3所以整棵树根是3。中序里3在中间左边[9]是左子树右边[15, 20, 7]是右子树。二、核心思路递归切分每一次递归我们面对的都是“当前这一小棵子树”的两个遍历数组buildTree(preorder,inorder)步骤前序第一个元素当前子树的根。去中序里找根的位置rootIndex。rootIndex左边是左子树右边是右子树。根据左子树节点个数在前序里也切出左子树和右子树。递归构建左右子树。返回当前根节点。三、完整可运行代码无索引版最好理解importjava.util.Arrays;classTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intval){this.valval;}}publicclassBuildTree{// 主入口每次传当前子树的 preorder 和 inorderpublicstaticTreeNodebuildTree(int[]preorder,int[]inorder){// 递归出口数组为空说明这个子树没有节点if(preorder.length0)returnnull;// 1. 前序第一个就是根introotValpreorder[0];TreeNoderootnewTreeNode(rootVal);// 2. 在中序里找根的位置introotIndex0;for(inti0;iinorder.length;i){if(inorder[i]rootVal){rootIndexi;break;}}// 3. 切左子树// 中序根左边 [0, rootIndex)int[]leftInorderArrays.copyOfRange(inorder,0,rootIndex);// 前序根后面紧跟左子树长度是 rootIndex所以 [1, 1 rootIndex)int[]leftPreorderArrays.copyOfRange(preorder,1,1rootIndex);// 4. 切右子树// 中序根右边 [rootIndex 1, end)int[]rightInorderArrays.copyOfRange(inorder,rootIndex1,inorder.length);// 前序左子树之后就是右子树 [1 rootIndex, end)int[]rightPreorderArrays.copyOfRange(preorder,1rootIndex,preorder.length);// 5. 递归root.leftbuildTree(leftPreorder,leftInorder);root.rightbuildTree(rightPreorder,rightInorder);returnroot;}// 测试用前序打印树publicstaticvoidprintPreorder(TreeNoderoot){if(rootnull)return;System.out.print(root.val );printPreorder(root.left);printPreorder(root.right);}// main 函数publicstaticvoidmain(String[]args){int[]preorder{3,9,20,15,7};int[]inorder{9,3,15,20,7};TreeNoderootbuildTree(preorder,inorder);System.out.print(重建后的树前序遍历输出: );printPreorder(root);// 输出: 3 9 20 15 7}}四、重点左子树是怎么切出来的以第一次调用为例preorder[3,9,20,15,7]inorder[9,3,15,20,7]根是3。在中序里3的索引是1inorder[9,3,15,20,7]^^01-rootIndex中序结构左子树 | 根 | 右子树 [9] | 3 | [15, 20, 7]所以leftInorderArrays.copyOfRange(inorder,0,rootIndex);// 取索引 [0, 1) [9]前序结构根 | 左子树 | 右子树 3 | 9 | 20, 15, 7根占掉索引0左子树紧跟在后面长度是rootIndex 1个leftPreorderArrays.copyOfRange(preorder,1,1rootIndex);// 取索引 [1, 2) [9]于是递归左子树时传buildTree([9],[9])右子树同理rightInorderArrays.copyOfRange(inorder,rootIndex1,inorder.length);// [2, 5) [15, 20, 7]rightPreorderArrays.copyOfRange(preorder,1rootIndex,preorder.length);// [2, 5) [20, 15, 7]递归右子树时传buildTree([20,15,7],[15,20,7])五、递归过程直观图原始pre [3, 9, 20, 15, 7] ino [9, 3, 15, 20, 7] 根 3拆左: pre[9], ino[9] - 节点9 右: pre[20,15,7], ino[15,20,7] - 根20处理右pre [20, 15, 7] ino [15, 20, 7] 根 20 左: pre[15], ino[15] - 节点15 右: pre[7], ino[7] - 节点7最终树3 / \ 9 20 / \ 15 7六、参数到底什么意思这版递归函数buildTree(int[]preorder,int[]inorder)参数含义preorder当前这棵子树的“根左右”遍历结果inorder当前这棵子树的“左根右”遍历结果没有那些preStart、preEnd、inStart、inEnd因为每次直接把数组切成新的子数组传给下一层。牺牲一点空间换直观。七、补充为什么题目通常保证节点值不重复因为我们要靠if(inorder[i]rootVal)去中序里找根的位置。如果有重复值就不知道找哪一个树可能不唯一也不能这样直接还原。八、复杂度这版数组拷贝时间约O(n^2)最坏情况比如树退化为链表不断拷贝数组线性查找根。如果用HashMap存中序值到索引的映射并改用索引范围不拷贝数组可以优化到O(n)。空间O(n^2)最坏拷贝数组的开销递归栈O(n)。索引版空间更优。但学习时先理解“前序找根、中序切左右”这个本质比一开始追求最优参数形式更重要。一句话总结前序告诉你“现在谁是根”中序告诉你“根的左边归左树、右边归右树”递归切下去树就出来了。

企业数字化 ERP 产品动态

相关推荐

【数据治理（6）】DataOps 不是调度工具，而是让数据产品长期可信的运行机制

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

理解 GC Roots：对象为什么不能被回收

【数据治理（2）】数据工程生命周期：从数据产生到价值实现的判断框架

下载 | Win11 23H2正式版最新ISO系统映像 (22631.7654、多合一版本)-修复系统问题

⏩ 【资源A010】Win11 23H2正式版最新原版ISO系统映像🔶 Windows 11 23H2 正式版渠道的最新ISO系统映像，2026年10月更新版本已上传，资源链接内会定期跟进，更新ISO版本，建议收藏备用！Win11 23H2最新ISO映像下… · 2026/11/3 2:49:27

* LangGraph 基础入门：定位、核心概念与第一个可运行图

一、LangGraph总览 LangGraph 运行时底层基于自研的 Pregel 运行时，其核心思想借鉴了 Google Pregel 计算模型，用于组织和执行复杂的图计算流程。 1.0. LangGraph和LangChain的版本迭代及定位 LangChain 1.x 的定位发生了明显变化：旧式 Ch… · 2026/11/3 2:49:27

squish6.3自动化代码用例编写

一、用例函数之 init() 和 cleanup() 附加模式下一定要注意用例结束后的恢复工作，否则会造成后续用例失败； squish中默认提供了init和cleanup函数： init()方法失败，main()方法不执行，cleanup()方法会执行&#xff1b… · 2026/11/3 2:49:27

【元宝搜索开发者征文大赛】少点幻觉，多点搜索：我做了个政策过期检测器

目录前言 1 起因：AI 拿着一份过期三年的补贴政策，差点让他报错材料 2 为什么治「政策幻觉」，非得用元宝搜索不可 3 先把钥匙拿到手：元宝搜索 API Key 开通全流程 3.1 开通服务，把版本选对 3.2 先用 curl 打通一… · 2026/11/3 2:49:27

大模型小白必看：收藏这份AI Agent底层逻辑解析，轻松上手构建智能应用

本文深入解析AI Agent的核心运作机制，揭示其本质为“调用工具的循环系统”。文章详细拆解了Agent的四大核心组件：Loop循环机制、Tools工具调用能力、Memory记忆模块以及Harness调度管控模块，并阐述了它们如何协同工作以实现智能任务执行。通过… · 2026/11/3 2:49:27

从０开始学架构－结束语：坚持，成就你的技术梦想

“从0开始学架构”专栏历经4个月的时间，现在到了跟你说再见的时候了。一路走来，非常感谢你的坚持。看到专栏的内容能够帮助你理解架构设计这个看起来高大上的技术，我非常欣慰，也算完成了自己3年前的一个心愿：帮助更多同学更快更好地掌握架构设计的技术。专栏的结束意味着… · 2026/11/3 2:48:27