京公网安备11010502063487号给定一棵二叉树的中序遍历序列和后序遍历序列（值互不相同），重建出这棵树：postorder 的最后一个元素是根（后序是"左、右、根"），在 inorder 里定位这个根，就能把序列切成左右两半分别递归。一个真实会犯的错误是照搬上一题"前序定根"的思路，误把 postorder[0] 当成根——但后序的根在最后不在最前。本文用 2000 组随机二叉树验证这个错误有多常见，给出正确写法、5 种语言实现，以及 postorder 末尾定根的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一棵二叉树的中序遍历序列和后序遍历序列（值互不相同），重建出这棵二叉树。一共 5 组用例，覆盖：官方示例、单结点、两结点、三结点的左链和右链：
inorder=[9, 3, 15, 20, 7] postorder=[9, 15, 7, 20, 3] → [3,9,20,null,null,15,7] inorder=[-1] postorder=[-1] → [-1] inorder=[2, 1] postorder=[2, 1] → [1,2] inorder=[1, 2, 3] postorder=[3, 2, 1] → [1,null,2,null,3] inorder=[3, 2, 1] postorder=[3, 2, 1] → [1,2,null,3]
上一题"从前序与中序构造二叉树"的做法是取 preorder 的第一个元素当根。如果照搬这个思路来做本题、直接取 postorder[0] 当根，那就错了——后序遍历是"左、右、根"，根在最后一个位置，不是第一个。用官方示例验证：
inorder=[9, 3, 15, 20, 7] postorder=[9, 15, 7, 20, 3]\n正确写法（root = postorder[-1]） → [3,9,20,null,null,15,7]\n陷阱写法（root = postorder[0]） → 程序崩溃：list index out of range
这个反例甚至没能重建出一棵"看起来正常但错误"的树，而是直接崩溃了——因为 postorder[0]=9 在 inorder 里的位置是 0（最左边），按这个位置切分出的"左子树"区间是空的，但后面递归传下去的 postorder 下标范围却没跟着对齐，很快就会越界。为了确认这不是巧合，做了一次随机测试：生成 2,000 组随机二叉树（结点数 1 到 10，值互不相同）：
2,000 组随机树，陷阱写法（postorder[0] 当根）：\n直接崩溃（数组下标越界） 1,099 组，占 55.0%\n没崩溃但重建出错误的树 701 组，占 35.1%\n碰巧和正确结果一致 200 组，占 10.0%（几乎都是结点数很少的简单树）
超过一半直接崩溃，三分之一会静静地重建出错误的树，只有一成的简单情况碰巧对。根本原因是：postorder 的"根在最后"和 preorder 的"根在最前"是两件不能互相替换的事，切分左右子树时对应的下标范围也完全不同，不能照搬。
先把 inorder 的值到下标的映射建成一张哈希表。递归函数 helper(inL, inR, postL, postR) 每次处理 inorder 的 [inL, inR] 段和 postorder 的 [postL, postR] 段：postorder[postR]（最后一个）是这一段的根，在 inorder 里查到根的位置 mid，左子树的结点数是 mid - inL，据此切出 postorder 里对应左右子树的区间，递归重建。时间 O(n)，空间 O(n)。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def build_tree(inorder, postorder): idx = {v: i for i, v in enumerate(inorder)} def helper(in_l, in_r, post_l, post_r): if in_l > in_r: return None root_val = postorder[post_r] # postorder 的最后一个就是这段的根 root = TreeNode(root_val) mid = idx[root_val] left_size = mid - in_l root.left = helper(in_l, mid - 1, post_l, post_l + left_size - 1) root.right = helper(mid + 1, in_r, post_l + left_size, post_r - 1) return root return helper(0, len(inorder) - 1, 0, len(postorder) - 1)
$ python3 solution.py inorder=[9, 3, 15, 20, 7] postorder=[9, 15, 7, 20, 3] → [3,9,20,null,null,15,7] inorder=[-1] postorder=[-1] → [-1] inorder=[2, 1] postorder=[2, 1] → [1,2] inorder=[1, 2, 3] postorder=[3, 2, 1] → [1,null,2,null,3] inorder=[3, 2, 1] postorder=[3, 2, 1] → [1,2,null,3]
Java · 解法代码class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { Map<Integer, Integer> idx = new HashMap<>(); for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i); return helper(postorder, 0, inorder.length - 1, 0, postorder.length - 1, idx); } private TreeNode helper(int[] postorder, int inL, int inR, int postL, int postR, Map<Integer, Integer> idx) { if (inL > inR) return null; int rootVal = postorder[postR]; // postorder 的最后一个就是这段的根 TreeNode root = new TreeNode(rootVal); int mid = idx.get(rootVal); int leftSize = mid - inL; root.left = helper(postorder, inL, mid - 1, postL, postL + leftSize - 1, idx); root.right = helper(postorder, mid + 1, inR, postL + leftSize, postR - 1, idx); return root; } }
$ javac -d build Main.java && java -cp build Main inorder=[9, 3, 15, 20, 7] postorder=[9, 15, 7, 20, 3] → [3,9,20,null,null,15,7] inorder=[-1] postorder=[-1] → [-1] inorder=[2, 1] postorder=[2, 1] → [1,2] inorder=[1, 2, 3] postorder=[3, 2, 1] → [1,null,2,null,3] inorder=[3, 2, 1] postorder=[3, 2, 1] → [1,2,null,3]
Go · 解法代码func buildTree(inorder []int, postorder []int) *TreeNode { idx := map[int]int{} for i, v := range inorder { idx[v] = i } var helper func(inL, inR, postL, postR int) *TreeNode helper = func(inL, inR, postL, postR int) *TreeNode { if inL > inR { return nil } rootVal := postorder[postR] // postorder 的最后一个就是这段的根 root := &TreeNode{Val: rootVal} mid := idx[rootVal] leftSize := mid - inL root.Left = helper(inL, mid-1, postL, postL+leftSize-1) root.Right = helper(mid+1, inR, postL+leftSize, postR-1) return root } return helper(0, len(inorder)-1, 0, len(postorder)-1) }
$ go run solution.go inorder=[9, 3, 15, 20, 7] postorder=[9, 15, 7, 20, 3] → [3,9,20,null,null,15,7] inorder=[-1] postorder=[-1] → [-1] inorder=[2, 1] postorder=[2, 1] → [1,2] inorder=[1, 2, 3] postorder=[3, 2, 1] → [1,null,2,null,3] inorder=[3, 2, 1] postorder=[3, 2, 1] → [1,2,null,3]
JavaScript · 解法代码function buildTree(inorder, postorder) { const idx = new Map(); inorder.forEach((v, i) => idx.set(v, i)); function helper(inL, inR, postL, postR) { if (inL > inR) return null; const rootVal = postorder[postR]; // postorder 的最后一个就是这段的根 const root = new TreeNode(rootVal); const mid = idx.get(rootVal); const leftSize = mid - inL; root.left = helper(inL, mid - 1, postL, postL + leftSize - 1); root.right = helper(mid + 1, inR, postL + leftSize, postR - 1); return root; } return helper(0, inorder.length - 1, 0, postorder.length - 1); }
$ node run.js inorder=[9, 3, 15, 20, 7] postorder=[9, 15, 7, 20, 3] → [3,9,20,null,null,15,7] inorder=[-1] postorder=[-1] → [-1] inorder=[2, 1] postorder=[2, 1] → [1,2] inorder=[1, 2, 3] postorder=[3, 2, 1] → [1,null,2,null,3] inorder=[3, 2, 1] postorder=[3, 2, 1] → [1,2,null,3]
C++ · 解法代码class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { unordered_map<int,int> idx; for (int i = 0; i < (int)inorder.size(); i++) idx[inorder[i]] = i; return helper(postorder, 0, inorder.size()-1, 0, postorder.size()-1, idx); } private: TreeNode* helper(vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int,int>& idx) { if (inL > inR) return nullptr; int rootVal = postorder[postR]; // postorder 的最后一个就是这段的根 TreeNode* root = new TreeNode(rootVal); int mid = idx[rootVal]; int leftSize = mid - inL; root->left = helper(postorder, inL, mid-1, postL, postL+leftSize-1, idx); root->right = helper(postorder, mid+1, inR, postL+leftSize, postR-1, idx); return root; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin inorder=[9, 3, 15, 20, 7] postorder=[9, 15, 7, 20, 3] → [3,9,20,null,null,15,7] inorder=[-1] postorder=[-1] → [-1] inorder=[2, 1] postorder=[2, 1] → [1,2] inorder=[1, 2, 3] postorder=[3, 2, 1] → [1,null,2,null,3] inorder=[3, 2, 1] postorder=[3, 2, 1] → [1,2,null,3]
共 5 组用例（含边界），以 Python 结果为基准逐组比对：\n Python 通过 5/5\n Java 通过 5/5\n Go 通过 5/5\n JavaScript 通过 5/5\n C++ 通过 5/5
Python 版本的哈希表实现另外和一个独立写的、每次现查 inorder.index() 的版本做了随机对拍：
随机对拍 5,000 组（结点数 0 到 10 的随机二叉树，值互不相同），哈希表版与现查 index 版的结果全部一致，0 处不一致。
另外四种语言只在上面 5 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 inorder=[9,3,15,20,7]、postorder=[9,15,7,20,3]：每一步先从 postorder 段的末尾取出根，再去 inorder 段里定位这个根，把左右两侧分别切给左右子树递归处理。蓝色是当前正在处理的区间，绿色是已经确定归属的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。