105. 从前序与中序遍历构造二叉树（C语言高质量题解）

一、题目描述给定两个整数数组preorder和inorderpreorder是二叉树的前序遍历inorder是同一棵树的中序遍历请构造二叉树并返回其根节点。 二、核心思路必须吃透1️⃣ 遍历特性前序遍历root - left - right中序遍历left - root - right关键结论前序数组第一个元素一定是当前子树的根在中序中找到这个根就能划分左右子树2️⃣ 图解理解preorder: [3, 9, 20, 15, 7] inorder: [9, 3, 15, 20, 7] 步骤 1. root 3 2. 在 inorder 中找到 3 inorder 被分成 [9] | 3 | [15, 20, 7] 左子树大小 1 preorder 对应拆分 [3 | 9 | 20,15,7] ↑ 左子树 三、递归本质模板定义函数build(preL, preR, inL, inR)表示 用 preorder[preL..preR] 和 inorder[inL..inR] 构造树 划分规则root preorder[preL] k root 在 inorder 中的位置 leftSize k - inL 左子树 preorder: [preL1, preLleftSize] inorder: [inL, k-1] 右子树 preorder: [preLleftSize1, preR] inorder: [k1, inR] 四、C语言最优实现O(n)#include stdlib.h // 值范围 -3000~3000 int indexMap[6001]; struct TreeNode* build(int* preorder, int preL, int preR, int* inorder, int inL, int inR) { if (preL preR) return NULL; int rootVal preorder[preL]; struct TreeNode* root (struct TreeNode*)malloc(sizeof(struct TreeNode)); root-val rootVal; int k indexMap[rootVal 3000]; int leftSize k - inL; root-left build(preorder, preL 1, preL leftSize, inorder, inL, k - 1); root-right build(preorder, preL leftSize 1, preR, inorder, k 1, inR); return root; } struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) { // 建哈希表 for (int i 0; i inorderSize; i) { indexMap[inorder[i] 3000] i; } return build(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1); }⚠️ 五、常见错误面试高频坑❌ 1. 每次线性查找 rootfor (int i inL; i inR; i) 复杂度退化为O(n²)必卡❌ 2. 区间写错最致命重点记左子树 preorder: preL1 → preLleftSize❌ 3. 忘记终止条件if (preL preR) return NULL;⏱️ 六、复杂度分析类型复杂度时间O(n)空间O(n) 七、模板总结强烈建议背下来二叉树构造类通用模板1. 前序定根 2. 中序找位置 3. 计算左子树大小 4. 递归构造左右子树 八、延伸题同一套路从中序与后序遍历构造二叉树根据前序和后序遍历构造二叉树 本质换个遍历本质不变 总结一句话前序找根中序分割递归构建 哈希优化这是二叉树构造问题的核心套路。