思路前序遍历顺序[根, 左子树…, 右子树…]第一个元素一定是根。中序遍历顺序[左子树…, 根, 右子树…]根将中序序列分为左右两部分。递归构造从前序取第一个元素作为根。在中序中找到根的位置 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本代码递归中已处理。