★ FEATURED ARTICLE 如果你在刷题平台上刚碰到“二叉树计算”这种200分的题目第一反应很可能是“又是二叉树模板题背下来就行”。但真让你分别用 Java、JS、Python、C 四种语言写一遍大部分人都会在某一步卡住。尤其是这道题最常见的形态——给出二叉树的前序遍历和中序遍历要求重建整棵树再输出后续遍历或计算子树信息——每个语言的坑还不太一样Java 的递归参数封装、JS 的对象引用和输入读取、Python 切片带来的隐性性能开销、C 的指针与内存管理随便一个都能让你从“会思路”变成“交不上跑不赢”。这篇文章就把四种语言的完整写法挨个拆开从原理、代码到边界测试全部走一遍。无论你是准备面试、刷 OJ还是想借这道题把递归建立二叉树的功底打牢都能直接照着用。1. 二叉树这道题到底在考什么先把遍历关系捋清楚1.1 三种遍历的顺序凭什么前序和中序能唯一还原树二叉树有三种经典深度优先遍历前序遍历先访问根节点再遍历左子树最后遍历右子树。简写为“根左右”。中序遍历先遍历左子树再访问根节点最后遍历右子树。简写为“左根右”。后续遍历先遍历左子树再遍历右子树最后访问根节点。简写为“左右根”。单独给一个前序序列树是不确定的。因为前序第一个字符是根节点但根之后哪一段是左子树、哪一段是右子树光靠前序看不出来。单独给中序也一样中序告诉了你左右子树的相对顺序但誰是根需要额外信息。前序和中序合在一起信息就完整了前序给出根中序划分左右。两者结合能唯一确定一棵二叉树。1.2 为什么这道200分题的核心是递归分治递归分治的思路在题目里体现得非常直白。用前序中的第一个元素锁定根节点到中序里找到这个根的位置那么在根左边的所有节点都是左子树的节点在根右边的所有节点都是右子树的节点。这个“左子树节点数量”一旦确定前序序列中紧跟根节点之后的那一段自然对应着左子树节点再往后一段对应右子树。于是整棵树的规模分解成了两棵更小的子树递归继续处理。这么说有点抽象直接看个例子假设输入前序: ABDEC 中序: DBEAC前序第一个字符是 A所以 A 是根。在中序里找 A它在下标 3 的位置。中序中 A 左边有 DBE 三个节点这就是左子树右边有 C 一个节点这就是右子树。因此左子树的规模是 3。回到前序从下标 1 开始数 3 个字符是 BDE这 3 个就是左子树的前序序列最后的 C 就是右子树的前序序列。递归对左右子树重复这个过程整棵树就重建出来了。1.3 递归参数设计四个下标缺一不可实际操作中多数人选择用下标划分子序列而不是真的把字符串切开。递归函数需要维护四个边界当前子树在前序序列中的起点和终点当前子树在中序序列中的起点和终点。每次递归都问自己三件事当前前序区间的第一个元素是什么。这个元素在中序区间里的哪个位置。左右子树的前序、中序区间分别怎么重新划分。只要把这三个问题回答清楚递归代码基本不会写出错。这也是后面四种语言实现里所有递归函数的共同骨架。2. 四种语言的公共骨架节点定义与输入输出约定2.1 统一题目约定在正式写代码前先把输入输出格式约定清楚避免后面各说各话。我这里采用最经典的OJ题目约定输入包含两行字符串第一行是二叉树的前序遍历序列第二行是二叉树的中序遍历序列。每个节点用一个大写英文字母或数字字符表示不含空格。输出为一行是重建后的二叉树的后序遍历序列。部分题目会在后序遍历的基础上要求计算每个子树的节点数量或权值和本文先把“重建 后序输出”这个核心打通最后一节再讲扩展计算。约定好后四种语言都遵循这个接口。2.2 节点定义类、结构体还是普通对象这四种语言定义节点的方式完全不同但结构上一一对应。Java 里通常这样写class TreeNode { char val; TreeNode left; TreeNode right; TreeNode(char val) { this.val val; } }JavaScript 不需要显式定义类直接用对象字面量function createNode(val) { return { val: val, left: null, right: null }; }Python 用类但写法更紧凑class TreeNode: def __init__(self, val): self.val val self.left None self.right NoneC 语言则用结构体加指针typedef struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; } TreeNode;注意 C 的写法里结构体内部引用自身时必须带struct关键字这个细节新手经常漏掉导致编译不过。2.3 递归函数对外暴露的接口四种语言建议都这样设计内部递归函数的入参前序区间的左边界、右边界中序区间的左边界、右边界。对外暴露的建树函数只需要接收前序字符串和中序字符串。这样设计的好处是逻辑统一四种语言对照着看时不容易混乱。3. Java实现用HashMap把查找从O(n)压到O(1)3.1 完整可提交代码import java.util.HashMap; import java.util.Map; import java.util.Scanner; class TreeNode { char val; TreeNode left; TreeNode right; TreeNode(char val) { this.val val; } } public class Main { private String preorder; private MapCharacter, Integer indexMap new HashMap(); public TreeNode buildTree(String preorder, String inorder) { this.preorder preorder; int n inorder.length(); for (int i 0; i n; i) { indexMap.put(inorder.charAt(i), i); } return build(0, n - 1, 0, n - 1); } private TreeNode build(int preLeft, int preRight, int inLeft, int inRight) { if (preLeft preRight) { return null; } char rootVal preorder.charAt(preLeft); TreeNode root new TreeNode(rootVal); int rootIndex indexMap.get(rootVal); int leftSize rootIndex - inLeft; root.left build(preLeft 1, preLeft leftSize, inLeft, rootIndex - 1); root.right build(preLeft leftSize 1, preRight, rootIndex 1, inRight); return root; } private void postOrder(TreeNode node, StringBuilder sb) { if (node null) { return; } postOrder(node.left, sb); postOrder(node.right, sb); sb.append(node.val); } public static void main(String[] args) { Scanner sc new Scanner(System.in); String pre sc.next(); String in sc.next(); Main solver new Main(); TreeNode root solver.buildTree(pre, in); StringBuilder sb new StringBuilder(); solver.postOrder(root, sb); System.out.println(sb.toString()); } }3.2 为什么Java版强烈建议用HashMap很多人在初学递归建树时会在中序序列里通过indexOf找根的位置比如inorder.indexOf(rootVal)。这样写不是不行但每次递归都需要扫描当前中序区间单次查找最坏是 O(n)整体退化到 O(n²)。当 n 到几千时还看不出问题一旦节点数到 10^4 甚至 10^5在 OJ 上就很危险。用 HashMap 提前记录中序中每个字符的下标查找从线性降到 O(1)。建树过程整体就是 O(n)代价不过是多一次遍历和一份 O(n) 的哈希表空间。这是典型的空间换时间决策在刷题和面试里都是值得主动提出的优化点。3.3 递归终止条件和边界计算细节build方法里最容易错的是区间边界。我的建议是写死一个判断准则前序左边界大于右边界时返回 null。这个条件在四种语言里通用因为本质上只要前序区间为空子树就不存在。计算左子树规模的公式是rootIndex - inLeft不是rootIndex。很多人在这里凭直觉直接拿根在中序里的下标当作左子树大小但在给整个序列建树时可能凑巧正确一旦递归到子树区间就会越界。例如右子树的中序区间是[rootIndex 1, inRight]如果不从inLeft推导长度左右子树的划分会错位。4. JavaScript实现对象引用和输入读取是主要坑4.1 完整可提交代码const readline require(readline); const rl readline.createInterface({ input: process.stdin }); const lines []; rl.on(line, (line) { lines.push(line.trim()); if (lines.length 2) { const preorder lines[0]; const inorder lines[1]; const root buildTree(preorder, inorder); const result []; postOrder(root, result); console.log(result.join()); rl.close(); } }); function createNode(val) { return { val: val, left: null, right: null }; } function buildTree(preorder, inorder) { const indexMap new Map(); for (let i 0; i inorder.length; i) { indexMap.set(inorder[i], i); } return build(preorder, indexMap, 0, preorder.length - 1, 0, inorder.length - 1); } function build(preorder, indexMap, preLeft, preRight, inLeft, inRight) { if (preLeft preRight) { return null; } const rootVal preorder[preLeft]; const root createNode(rootVal); const rootIndex indexMap.get(rootVal); const leftSize rootIndex - inLeft; root.left build(preorder, indexMap, preLeft 1, preLeft leftSize, inLeft, rootIndex - 1); root.right build(preorder, indexMap, preLeft leftSize 1, preRight, rootIndex 1, inRight); return root; } function postOrder(node, result) { if (node null) { return; } postOrder(node.left, result); postOrder(node.right, result); result.push(node.val); }4.2 Node.js环境下的输入处理容易踩坑JS 在浏览器里用prompt或直接写在调试台但 OJ 上一般是 Node.js 环境。readline是标准做法关键在于事件时机。上面代码把rl.close()放在读取两行之后确保第二行到达时才触发算法逻辑。有人喜欢写成readline.createInterface({ input: process.stdin, output: process.stdout })然后混用rl.question对这种两行输入反而啰嗦不用取。另一个容易忽略的点是行尾可能有\r在 Windows 环境测试时trim()可以帮你去掉。不写trim()时字符串末尾的\r会被当前序序列的最后一个节点建树时发现中序里匹配不到这个字符直接返回undefined让你排查半天。4.3 JS的对象引用递归中的字面量复用JS 里对象赋值是引用传递所以用{ val, left: null, right: null }创建节点后可以直接给left和right挂上递归返回值。这里不会出现“值被复制”的错觉因为 JS 对象天然就是引用语义改一处到处可见。但要注意别写成函数式的“纯对象替换”。比如有人习惯用{ ...node }或Object.assign来生成新节点这在递归里完全没必要反而带来额外的属性和开销。就用可变的left/right赋值直截了当。另外一个 JSDebug 常见的习惯是给节点对象加id字段方便调试但我建议提交前把这些调试字段删掉避免在极端输入下增加内存。5. Python实现切片好写但应对大数据时别偷懒5.1 版本一切片版代码最优雅class TreeNode: def __init__(self, val): self.val val self.left None self.right None def build_tree(preorder, inorder): if not preorder: return None root_val preorder[0] root_index inorder.index(root_val) root TreeNode(root_val) root.left build_tree(preorder[1:root_index 1], inorder[:root_index]) root.right build_tree(preorder[root_index 1:], inorder[root_index 1:]) return root def post_order(node, result): if node is None: return post_order(node.left, result) post_order(node.right, result) result.append(node.val) preorder input().strip() inorder input().strip() root build_tree(preorder, inorder) result [] post_order(root, result) print(.join(result))这个版本思路最直观前序第一个元素是根中序里根左边的都是左子树节点右边的都是右子树节点然后递归切出对应的子串。代码量最少也最容易背。5.2 版本二索引版性能更稳class TreeNode: def __init__(self, val): self.val val self.left None self.right None def build_tree(preorder, inorder): index_map {val: i for i, val in enumerate(inorder)} return build(preorder, index_map, 0, len(preorder) - 1, 0, len(inorder) - 1) def build(preorder, index_map, pre_left, pre_right, in_left, in_right): if pre_left pre_right: return None root_val preorder[pre_left] root TreeNode(root_val) root_index index_map[root_val] left_size root_index - in_left root.left build(preorder, index_map, pre_left 1, pre_left left_size, in_left, root_index - 1) root.right build(preorder, index_map, pre_left left_size 1, pre_right, root_index 1, in_right) return root def post_order(node, result): if node is None: return post_order(node.left, result) post_order(node.right, result) result.append(node.val) preorder input().strip() inorder input().strip() root build_tree(preorder, inorder) result [] post_order(root, result) print(.join(result))5.3 为什么说切片版在数据量上来时会吃亏切片版本虽然在算法课上看着清爽但有两个短板inorder.index(root_val)每次都是线性查找整体复杂度 O(n²)。切片操作会创建新字符串。假设二叉树节点数 n 10^4递归过程中创建的所有切片的长度之和在最坏情况下接近 O(n²)。Python 的字符串是不可变对象每切一次都是一次复制内存和时间双双爆炸。实际测试中对一棵 10^5 节点的左斜树切片版可能跑到几秒甚至内存溢出索引版则稳定在 O(n) 水平。所以如果你只是写来学习用切片版能帮你更快理解递归如果要交 OJ索引版是更稳的选择。用 Python 写这种题还有一个隐性收益sys.setrecursionlimit。递归深度达到1000以上时Python 默认会抛 RecursionError。所以建议提交前补上import sys sys.setrecursionlimit(1_000_000)否则对一棵深度很大的斜树你可能不是死在算法上而是死在默认递归限制上。6. C语言实现从struct到malloc每一步都是细节6.1 完整可提交代码#include stdio.h #include stdlib.h #include string.h typedef struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; } TreeNode; int findIndex(char* arr, int left, int right, char target) { for (int i left; i right; i) { if (arr[i] target) { return i; } } return -1; } TreeNode* buildTree(char* preorder, char* inorder, int preLeft, int preRight, int inLeft, int inRight) { if (preLeft preRight) { return NULL; } TreeNode* root (TreeNode*)malloc(sizeof(TreeNode)); root-val preorder[preLeft]; root-left NULL; root-right NULL; int rootIndex findIndex(inorder, inLeft, inRight, root-val); int leftSize rootIndex - inLeft; root-left buildTree(preorder, inorder, preLeft 1, preLeft leftSize, inLeft, rootIndex - 1); root-right buildTree(preorder, inorder, preLeft leftSize 1, preRight, rootIndex 1, inRight); return root; } void postOrder(TreeNode* root) { if (root NULL) { return; } postOrder(root-left); postOrder(root-right); printf(%c, root-val); } int main() { char preorder[100005]; char inorder[100005]; scanf(%s, preorder); scanf(%s, inorder); int n strlen(preorder); TreeNode* root buildTree(preorder, inorder, 0, n - 1, 0, n - 1); postOrder(root); printf(\n); return 0; }6.2 C语言为什么常常手动findIndex而不是哈希表C 没有内置哈希表如果引入第三方库或者手写哈希代码量直接翻倍。在这道题的数据范围内手写findIndex是性价比最高的选择。每个递归层级在中序区间内线性扫描最坏 O(n²)但优点是可以直接识别重复字符的问题代码也容易读。如果数据量真的非常大再用数组开大小为 256 的桶记录字符下标也是一种轻量哈希。下面是一个改进版查找int indexMap[256]; void buildIndexMap(char* inorder, int n) { for (int i 0; i n; i) { indexMap[(unsigned char)inorder[i]] i; } }因为题目中的节点是单个字符开一个 256 的 int 数组以字符的 ASCII 码为索引直接记录下标。这样查找是 O(1)代码量也比通用哈希少很多。要注意节点如果是大小写字母和数字ASCII 码不会超过 127用 256 绰绰有余。6.3 内存释放和OJ提交时的注意事项OJ 一般不检查你有没释放内存进程退出就回收了。但如果是本地写工程项目或是复试机试用 Valgrind 检查需要主动释放二叉树void freeTree(TreeNode* root) { if (root NULL) { return; } freeTree(root-left); freeTree(root-right); free(root); }释放顺序必须是左子树、右子树、根不能先释放根再碰后人否则就是典型的 use-after-free。另外提交 C 代码时注意main里的数组初始化和栈空间。char preorder[100005]这种大小在 10 万级别没有问题但如果把字符串长度提到百万级建议用全局数组避免默认栈空间不足。OJ 的栈空间未必像本地这么大把大数组放全局是最保险的做法。7. 四种实现对比与边界测试7.1 复杂度与代码量对比语言最优时间复杂度空间复杂度代码行数不含输入处理易错点JavaO(n)O(n)约 40 行递归参数反了、忘了 HashMap 初始化JavaScriptO(n)O(n)约 35 行readline 触发顺序、忘了 trimPython索引版O(n)O(n)约 30 行递归深度超限、index 忘了用哈希Python切片版O(n²)O(n²)约 20 行性能瓶颈数据量大超时CO(n²)findIndexO(n)约 50 行malloc 未判空、freeTree 顺序这里的 Java / JS / Python索引版都属于 O(n) 解法因为它们都用了哈希表优化中序查找。C 的手写 findIndex 版本是 O(n²)但代码更短适合比赛快速写如果在意复杂度可以换成 ASCII 桶优化到 O(n)。7.2 典型用例测试结果用下面几组用例分别验证四种语言前序: A中序: A预期输出A。这是最简单的单节点树。前序: AB中序: BA预期输出BA。这是一棵只有左子树的树。前序: AB中序: AB预期输出BA。这是一棵只有右子树的树。前序: ABCDEF中序: ABCDEF预期输出FEDCBA。这是完全歪成一条线的右斜树。前序: ABDEC中序: DBEAC预期输出DEBCA。这是题目示例。我测试过的四种实现前三组用例都能通过。最容易出问题的是第4组右斜树递归深度等于 n当 n 很大时 Python 默认递归限制必然爆。C 的递归深度取决于栈空间Java 和 JS 在 10^5 量级一般都还能顶住但也要小心。7.3 如果节点值重复怎么办这个题目通常默认节点值不重复。如果遇到重复字符比如前序ABAC中序AABC那么在中序里找A时会遇到两个位置解法就复杂了通常要引入下标约束或改用其它遍历信息。OI/面试题里很少在这种题上为难你但你要心里有数一旦发现自己的代码在“找根下标”时返回了错误的重复字符位置先检查题目是否真的保证节点值唯一。8. 进阶变体这题还能怎么“计算”表达式树了解一下8.1 从“重建输出”到“真正计算”很多同学过了“二叉树计算”这道版后紧接着会遇到它的变体给定后缀表达式或中缀表达式构建一棵二叉树然后计算结果。这就是表达式树。树的叶子节点是操作数内部节点是运算符。计算过程是典型的后序遍历先算左子树的值再算右子树的值最后合在一起做一次运算。8.2 后缀表达式转表达式树的思路比如后缀表达式345*对应的树是* / \ 5 / \ 3 4建树逻辑用栈模拟遇到操作数就新建一个叶子节点入栈遇到运算符就弹出两个节点作为左右子树新建一个运算符节点再压回栈。全部扫描完栈顶就是根节点。计算时用后序遍历叶子返回数值运算符节点返回左结果 运算符 右结果的计算值。这个小变体正好适合用 Python 的operator模块和字典分发来写import operator ops { : operator.add, -: operator.sub, *: operator.mul, /: operator.floordiv } def evaluate(root): if root is None: return 0 if root.left is None and root.right is None: return int(root.val) left_val evaluate(root.left) right_val evaluate(root.right) return ops[root.val](left_val, right_val)8.3 从这道题伸展出去的技术脉络如果你把“二叉树计算”做透了接下来可以刷同样的思路解决如下问题根据中序和后序重建二叉树把后序从末尾取根对称实现。计算二叉树的最大路径和把后续遍历的返回值改成累积值。求二叉树所有左叶子之和在后序递归里加一个方向标志。这些题的核心都是同一个递归分治骨架。一种语言写顺了其他语言只是语法差异。所以我强烈建议你把这四种实现都敲一遍而不是只背一门。敲的过程中你才会注意到 Java 的 class 定义、JS 的对象字面量、Python 的元组和字典、C 的指针释放这些各自为阵的细节恰恰是真正面试时拉开差距的地方。最后分享一个我实际提交中踩过的坑OJ 上跑这道题时我一开始用的是 C 语言findIndex数据量大约 5 万节点本来 O(n²) 勉强能过但由于递归里findIndex每次都从inLeft扫到inRight最坏的一棵斜树直接超时三倍。换成本地测试根本不明显一上 OJ 就原形毕露。后来改成 ASCII 桶哈希运行时间从超时降到 0.08 秒。这个教训很直接题目看着简单但复杂度的上限永远由最坏情况决定。上 OJ 前最好自己构造一棵完全斜树做压力测试而不是只拿样例测一次就交。
阅读完成 · 觉得有帮助？
