📌 一、题目描述
给定两个数组：
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 [k+1 ...... inR] 左子树 根 右子树3️⃣ 如何切分 postorder？（核心难点）
设：
leftSize = k - inL那么：
| 子树 | inorder 区间 | postorder 区间 |
|---|---|---|
| 左子树 | [inL, k-1] | [postL, postL + leftSize - 1] |
| 右子树 | [k+1, 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); }📊 四、复杂度分析
❌ 当前实现
查找 root：O(n)
总体复杂度：
O(n^2)🚀 优化（推荐面试说）
使用哈希表记录 inorder 下标：
value -> index👉 查找变 O(1)
✅ 优化后复杂度
时间复杂度：O(n) 空间复杂度：O(n)⚠️ 五、常见错误总结
❌ 错误 1：把 postorder[0] 当根
👉 根在最后一个！
❌ 错误 2：区间乱写
👉 强烈建议统一：
全部使用：左闭右闭 [L, R]❌ 错误 3：右子树没减 1
postR - 1 // 很多人忘❌ 错误 4：leftSize 写错
leftSize = k - inL; // 必须这样🧩 六、和 105 题的关系（面试重点）
| 题目 | 根节点位置 |
|---|---|
| 前序 + 中序 | preorder[preL] |
| 中序 + 后序 | postorder[postR] |
🎯 一句话模板
前序定头，后序定尾；中序划分左右子树
🚀 七、总结
这类题的本质只有三步：
确定根节点（前序头 / 后序尾）
在中序中定位根
按长度切分左右子树
如果你准备面试，这题建议做到：
✅ 能手写递归版本
✅ 能口述区间划分
✅ 能说出 O(n) 优化
