[特殊字符]【LeetCode 106】从中序与后序遍历构造二叉树（C语言详解｜递归+区间划分）

一、题目描述给定两个数组inorder中序遍历左 → 根 → 右postorder后序遍历左 → 右 → 根要求构造并返回这棵二叉树 示例输入 inorder [9,3,15,20,7] postorder [9,15,7,20,3] 输出 3 / \ 9 20 / \ 15 7 二、核心思路这题本质就是✅利用遍历特性还原树结构⭐ 关键观察1️⃣ 后序遍历 → 找根节点后序左 → 右 → 根最后一个元素一定是根节点root postorder[postR];2️⃣ 中序遍历 → 分割左右子树中序左 → 根 → 右找到 root 在 inorder 中的位置k[inL ...... k-1] k [k1 ...... inR] 左子树 根 右子树3️⃣ 如何切分 postorder核心难点设leftSize k - inL那么子树inorder 区间postorder 区间左子树[inL, k-1][postL, postL leftSize - 1]右子树[k1, inR][postL leftSize, postR - 1]✍️ 三、递归解法C语言实现✅ 完整代码#include stdlib.h // 二叉树结构定义 struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; // 查找 root 在 inorder 中的位置 int findIndex(int* inorder, int inL, int inR, int val) { for (int i inL; i inR; i) { if (inorder[i] val) return i; } return -1; } // 构建函数 struct TreeNode* build( int* inorder, int inL, int inR, int* postorder, int postL, int postR ) { // 终止条件 if (inL inR) return NULL; // 1️⃣ 根节点 int rootVal postorder[postR]; struct TreeNode* root (struct TreeNode*)malloc(sizeof(struct TreeNode)); root-val rootVal; root-left root-right NULL; // 2️⃣ 在 inorder 找位置 int k findIndex(inorder, inL, inR, rootVal); // 3️⃣ 左子树大小 int leftSize k - inL; // 4️⃣ 递归构建 root-left build(inorder, inL, k - 1, postorder, postL, postL leftSize - 1); root-right build(inorder, k 1, inR, postorder, postL leftSize, postR - 1); return root; } // 主函数 struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) { return build(inorder, 0, inorderSize - 1, postorder, 0, postorderSize - 1); } 四、复杂度分析❌ 当前实现查找 rootO(n)总体复杂度O(n^2) 优化推荐面试说使用哈希表记录 inorder 下标value - index 查找变 O(1)✅ 优化后复杂度时间复杂度O(n) 空间复杂度O(n)⚠️ 五、常见错误总结❌ 错误 1把 postorder[0] 当根 根在最后一个❌ 错误 2区间乱写 强烈建议统一全部使用左闭右闭 [L, R]❌ 错误 3右子树没减 1postR - 1 // 很多人忘❌ 错误 4leftSize 写错leftSize k - inL; // 必须这样 六、和 105 题的关系面试重点题目根节点位置前序 中序preorder[preL]中序 后序postorder[postR] 一句话模板前序定头后序定尾中序划分左右子树 七、总结这类题的本质只有三步确定根节点前序头 / 后序尾在中序中定位根按长度切分左右子树如果你准备面试这题建议做到✅ 能手写递归版本✅ 能口述区间划分✅ 能说出 O(n) 优化