京公网安备11010502063487号给定一棵二叉树的前序遍历序列和中序遍历序列（值互不相同），重建出这棵树：preorder 的第一个元素是根，在 inorder 里定位这个根，就能把序列切成左右两半分别递归。一个真实会犯的错误是把两个参数的调用顺序传反——函数内部逻辑没变，程序照样能跑，只是重建出一棵错误的树。本文用 2000 组随机二叉树验证这个错误有多常见，给出正确写法、5 种语言实现，以及 preorder 定根、inorder 切分左右的分步演示。
本文只用自己的话概括题意，完整约束以官方页面为准。给定一棵二叉树的前序遍历序列和中序遍历序列（值互不相同），重建出这棵二叉树。一共 5 组用例，覆盖：官方示例、单结点、两结点、三结点的左链和右链：
preorder=[3, 9, 20, 15, 7] inorder=[9, 3, 15, 20, 7] → [3,9,20,null,null,15,7] preorder=[-1] inorder=[-1] → [-1] preorder=[1, 2] inorder=[2, 1] → [1,2] preorder=[1, 2, 3] inorder=[1, 2, 3] → [1,null,2,null,3] preorder=[1, 2, 3] inorder=[3, 2, 1] → [1,2,null,3]
一个真实会犯的错误：把两个参数的顺序传反了——正确调用应该是 buildTree(preorder, inorder)，但如果写成 buildTree(inorder, preorder)，函数内部逻辑完全没变（用第一个参数的首元素当根，去第二个参数里定位切分），程序照样能跑，有时甚至能跑出一个"看起来正常"的树，只是这棵树是错的。用官方示例验证：
preorder=[3, 9, 20, 15, 7] inorder=[9, 3, 15, 20, 7]\n正确调用 buildTree(preorder, inorder) → [3,9,20,null,null,15,7]\n参数传反 buildTree(inorder, preorder) → [9,3,15,null,null,20,7]
参数传反之后，根变成了 9（本该是 3），整棵树的结构都不一样了，但函数并没有报错，看起来"跑成功了"。为了搞清楚这种错误有多容易被忽略，做了一次随机测试：生成 2,000 组随机二叉树（结点数 1 到 10，值互不相同），分别用正确顺序和传反顺序调用，统计三种结果：
2,000 组随机树，参数传反后：\n直接崩溃（数组下标越界） 1,081 组，占 54.1%\n没崩溃但重建出错误的树 559 组，占 28.0%\n碰巧和正确结果一致 360 组，占 18.0%（几乎都是结点数很少的简单树）
超过一半的情况会直接崩溃，因为传反之后"根"和"切分依据"不再互相匹配，下标计算很容易越界；另外 28% 不会崩溃，但静静地重建出一棵错误的树——这是最危险的情况，因为程序表面上"跑通了"。只有结点数很少、树的形状足够简单时，两种顺序才会碰巧给出一样的结果，容易让人在小规模测试时误以为写对了。
先把 inorder 的值到下标的映射建成一张哈希表，方便 O(1) 定位根。递归函数 helper(preL, preR, inL, inR) 每次处理 preorder 的 [preL, preR] 段和 inorder 的 [inL, inR] 段：preorder[preL] 是这一段的根，在 inorder 里查到根的位置 mid，左子树的结点数是 mid - inL，据此把 preorder 和 inorder 都切成对应的左右两段，递归重建。时间 O(n)，空间 O(n)（哈希表 + 递归栈）。Python、Java、Go、JavaScript、C++ 都是真实编译运行的，用同一组 5 个测试用例。
Python · 解法代码def build_tree(preorder, inorder): idx = {v: i for i, v in enumerate(inorder)} def helper(pre_l, pre_r, in_l, in_r): if pre_l > pre_r: return None root_val = preorder[pre_l] # preorder 的第一个就是这段的根 root = TreeNode(root_val) mid = idx[root_val] # 在 inorder 里找根的位置，切开左右子树 left_size = mid - in_l root.left = helper(pre_l + 1, pre_l + left_size, in_l, mid - 1) root.right = helper(pre_l + left_size + 1, pre_r, mid + 1, in_r) return root return helper(0, len(preorder) - 1, 0, len(inorder) - 1)
$ python3 solution.py preorder=[3, 9, 20, 15, 7] inorder=[9, 3, 15, 20, 7] → [3,9,20,null,null,15,7] preorder=[-1] inorder=[-1] → [-1] preorder=[1, 2] inorder=[2, 1] → [1,2] preorder=[1, 2, 3] inorder=[1, 2, 3] → [1,null,2,null,3] preorder=[1, 2, 3] inorder=[3, 2, 1] → [1,2,null,3]
Java · 解法代码class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { Map<Integer, Integer> idx = new HashMap<>(); for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i); return helper(preorder, 0, preorder.length - 1, 0, inorder.length - 1, idx); } private TreeNode helper(int[] preorder, int preL, int preR, int inL, int inR, Map<Integer, Integer> idx) { if (preL > preR) return null; int rootVal = preorder[preL]; // preorder 的第一个就是这段的根 TreeNode root = new TreeNode(rootVal); int mid = idx.get(rootVal); // 在 inorder 里找根的位置，切开左右子树 int leftSize = mid - inL; root.left = helper(preorder, preL + 1, preL + leftSize, inL, mid - 1, idx); root.right = helper(preorder, preL + leftSize + 1, preR, mid + 1, inR, idx); return root; } }
$ javac -d build Main.java && java -cp build Main preorder=[3, 9, 20, 15, 7] inorder=[9, 3, 15, 20, 7] → [3,9,20,null,null,15,7] preorder=[-1] inorder=[-1] → [-1] preorder=[1, 2] inorder=[2, 1] → [1,2] preorder=[1, 2, 3] inorder=[1, 2, 3] → [1,null,2,null,3] preorder=[1, 2, 3] inorder=[3, 2, 1] → [1,2,null,3]
Go · 解法代码func buildTree(preorder []int, inorder []int) *TreeNode { idx := map[int]int{} for i, v := range inorder { idx[v] = i } var helper func(preL, preR, inL, inR int) *TreeNode helper = func(preL, preR, inL, inR int) *TreeNode { if preL > preR { return nil } rootVal := preorder[preL] // preorder 的第一个就是这段的根 root := &TreeNode{Val: rootVal} mid := idx[rootVal] // 在 inorder 里找根的位置，切开左右子树 leftSize := mid - inL root.Left = helper(preL+1, preL+leftSize, inL, mid-1) root.Right = helper(preL+leftSize+1, preR, mid+1, inR) return root } return helper(0, len(preorder)-1, 0, len(inorder)-1) }
$ go run solution.go preorder=[3, 9, 20, 15, 7] inorder=[9, 3, 15, 20, 7] → [3,9,20,null,null,15,7] preorder=[-1] inorder=[-1] → [-1] preorder=[1, 2] inorder=[2, 1] → [1,2] preorder=[1, 2, 3] inorder=[1, 2, 3] → [1,null,2,null,3] preorder=[1, 2, 3] inorder=[3, 2, 1] → [1,2,null,3]
JavaScript · 解法代码function buildTree(preorder, inorder) { const idx = new Map(); inorder.forEach((v, i) => idx.set(v, i)); function helper(preL, preR, inL, inR) { if (preL > preR) return null; const rootVal = preorder[preL]; // preorder 的第一个就是这段的根 const root = new TreeNode(rootVal); const mid = idx.get(rootVal); // 在 inorder 里找根的位置，切开左右子树 const leftSize = mid - inL; root.left = helper(preL + 1, preL + leftSize, inL, mid - 1); root.right = helper(preL + leftSize + 1, preR, mid + 1, inR); return root; } return helper(0, preorder.length - 1, 0, inorder.length - 1); }
$ node run.js preorder=[3, 9, 20, 15, 7] inorder=[9, 3, 15, 20, 7] → [3,9,20,null,null,15,7] preorder=[-1] inorder=[-1] → [-1] preorder=[1, 2] inorder=[2, 1] → [1,2] preorder=[1, 2, 3] inorder=[1, 2, 3] → [1,null,2,null,3] preorder=[1, 2, 3] inorder=[3, 2, 1] → [1,2,null,3]
C++ · 解法代码class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { unordered_map<int,int> idx; for (int i = 0; i < (int)inorder.size(); i++) idx[inorder[i]] = i; return helper(preorder, 0, preorder.size()-1, 0, inorder.size()-1, idx); } private: TreeNode* helper(vector<int>& preorder, int preL, int preR, int inL, int inR, unordered_map<int,int>& idx) { if (preL > preR) return nullptr; int rootVal = preorder[preL]; // preorder 的第一个就是这段的根 TreeNode* root = new TreeNode(rootVal); int mid = idx[rootVal]; // 在 inorder 里找根的位置，切开左右子树 int leftSize = mid - inL; root->left = helper(preorder, preL+1, preL+leftSize, inL, mid-1, idx); root->right = helper(preorder, preL+leftSize+1, preR, mid+1, inR, idx); return root; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin preorder=[3, 9, 20, 15, 7] inorder=[9, 3, 15, 20, 7] → [3,9,20,null,null,15,7] preorder=[-1] inorder=[-1] → [-1] preorder=[1, 2] inorder=[2, 1] → [1,2] preorder=[1, 2, 3] inorder=[1, 2, 3] → [1,null,2,null,3] preorder=[1, 2, 3] inorder=[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 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 preorder=[3,9,20,15,7]、inorder=[9,3,15,20,7]：每一步先从 preorder 段的开头取出根，再去 inorder 段里定位这个根，把左右两侧分别切给左右子树递归处理。蓝色是当前正在处理的区间，绿色是已经确定归属（左子树/右子树/根）的结点。每一帧都是把上面的解法在这组输入上真实执行记录下来的。