递归分治与后序决策：二叉树四道高频难题全解析-北京尧图网络

二叉树系列写到这里终于到了Hot100里最见功力的几道题。前面那些遍历、层序、翻转、对称本质上是把二叉树当线性结构在处理而这一篇的四道题——从前序与中序遍历序列构造二叉树、路径总和III、二叉树的最近公共祖先、二叉树中的最大路径和全都在考递归的分治思维和后序收集思维。说白了前面是热身这几道才是二叉树递归真正拉开差距的地方。我刷这几道题的时候明显感觉到一个规律能做出来遍历题的人很多能把构造题和路径题讲明白的人少一半能说清楚最近公共祖先递归回溯过程的人更少。面试的时候这三句话几乎可以当作递归功底的试金石。这篇总结我尽量把每一道题的推导过程、代码细节、以及我踩过的坑都写清楚适合正在刷Hot100的Java选手也适合准备面试但总感觉递归会写不会讲的人。1. 整体设计与思路拆解1.1 四道题为什么要放在一起总结先聊聊这几道题的内在联系。如果只看标题它们好像是四个独立的知识点一个考数组切分一个考前缀和一个考公共祖先一个考路径最值。但实际刷下来你会发现它们共享同一个底层能力——递归函数返回什么、什么时候更新答案、如何把子树信息传递到父节点。具体来说这四道题可以分成两个阵营。第一阵营是前序构建从前序与中序遍历序列构造二叉树。它的核心动作发生在进入递归之前——先找到根节点确定左右子树的范围再去递归构建左右子树。这种模式我称之为分治构造它考验的是对数组边界的精确推导能力。第二阵营是后序决策路径总和III、最近公共祖先、最大路径和这三道题的核心动作都发生在递归返回之后——先递归处理完左右子树然后在当前节点收集子树信息并做出判断。这种模式我称之为后序收集。为什么要强调这个分类因为很多人在刷题时会陷入背模板的误区看到一个树的题不管三七二十一先写个递归然后在里面乱改一通。理解了前序构建和后序决策的区别之后你就知道递归函数应该在什么时候做主要工作代码写起来会顺很多。1.2 从遍历到构造递归能力的三个台阶我自己的体会是二叉树的递归可以分为三个台阶。第一个台阶是遍历——前序、中序、后序、层序。这个阶段你只需要知道访问节点的时机前序是进入节点时做事中序是左子树回来后做事后序是左右子树都回来后做事。大部分入门题最大深度、翻转二叉树、对称二叉树都停在这个层面。第二个台阶是构造——用某种遍历序列还原二叉树。这要求你从访问顺序反过来推导树的结构比如这一篇的从前序与中序遍历构造二叉树以及面试中同样常见的用前序和后序构造二叉树。这类题目的难点不是递归本身而是边界条件的推导。第三个台阶是决策——递归过程中维护全局答案或者利用后序信息做判断。路径总和III、最近公共祖先、最大路径和都属于这一类。它们要求你回答三个问题递归函数返回什么答案在什么时候更新子树信息如何向上传递把这三个台阶想清楚二叉树这块的递归你就基本上站住了。1.3 一个贯穿全篇的递归心法虽然每道题的解法不同但我刷完这几道题后总结出了一个通用的递归心法先写在前面后面每一道题都会用到写递归之前先明确三件事递归函数的返回值是什么是子树的根节点、计数结果、还是某个贡献值答案在哪里更新是进入节点时、左子树返回时还是左右子树都返回后边界条件是什么空节点返回什么叶子节点怎么处理这三件事想不清楚就动笔写出来的代码大概率是错的或者能过样例但说不清楚为什么对。后面讲每道题的时候我都会先把这三个问题解释一遍。2. 从前序与中序遍历序列构造二叉树数组切分的边界推导2.1 为什么前序中序可以唯一确定一棵二叉树先回答一个基础问题为什么拿前序序列和中序序列就能把一棵二叉树还原出来核心在于两个序列的信息是互补的。前序遍历的顺序是根 → 左子树 → 右子树所以前序序列的第一个元素一定是整棵树的根。中序遍历的顺序是左子树 → 根 → 右子树所以只要知道了根节点在中序序列中的位置它左边那一整段就全是左子树的节点右边那一整段就全是右子树的节点。这样我们就得到了一个递归结构用前序确定根用中序划分左右子树的节点集合然后左右子树各自又是一个前序中序的构造问题递归下去就能还原整棵树。这里有个关键点值得展开说前序序列里根之后紧跟着的若干连续元素恰好对应左子树的前序序列剩下的对应右子树的前序序列。这个若干的个数就是中序序列中根左侧元素的个数也就是左子树的节点数量。这个数量是连接两个序列的桥梁后面所有边界推导都围绕它展开。2.2 边界怎么推先写清楚每个区间的含义大多数人第一次写这题都会在边界上栽跟头。老实说我一开始也是拿几个例子硬试出来的后来才意识到应该先把每个区间变量定义清楚。假设递归函数处理的是这样一段区间前序序列的[preLeft, preRight]和中序序列的[inLeft, inRight]共同描述同一棵子树左右子树各有节点数量相等的区间。第一步找根节点。前序序列的preLeft位置就是根。第二步在中序序列中找到根节点位置rootIndex那么中序中左子树区间是[inLeft, rootIndex - 1]中序中右子树区间是[rootIndex 1, inRight]第三步计算左子树的节点数量int leftSize rootIndex - inLeft;第四步用leftSize去前序序列中切分左右子树前序中左子树区间是[preLeft 1, preLeft leftSize]前序中右子树区间是[preLeft leftSize 1, preRight]我把这四个区间写出来是因为很多错误的写法是把preLeft leftSize算成了preLeft rootIndex之类根源就在于没有想清楚leftSize是从中序推出来的、对应的是数量而preLeft leftSize是偏移后的位置。这两个东西概念上必须分清楚。2.3 完整实现HashMap预处理优化查找如果不做任何优化每轮递归都要在中序数组里线性扫描一遍找根节点位置总时间复杂度是 O(n²) 量级在 LeetCode 上也能过因为数据不是很大但面试时考官大概率会追问一句能不能优化。优化思路很简单先把中序序列里每个值对应的下标存进 HashMap这样查找根节点位置就是 O(1)。构造过程总时间降为 O(n)。这是我很推荐的做法因为代码量增加很少但复杂度直接从 O(n²) 降到了 O(n)面试观感完全不一样。来看完整实现class Solution { private MapInteger, Integer indexMap; public TreeNode buildTree(int[] preorder, int[] inorder) { int n preorder.length; indexMap new HashMap(); for (int i 0; i n; i) { indexMap.put(inorder[i], i); } return build(preorder, 0, n - 1, inorder, 0, n - 1); } private TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) { if (preLeft preRight) { return null; } int rootVal preorder[preLeft]; TreeNode root new TreeNode(rootVal); int rootIndex indexMap.get(rootVal); int leftSize rootIndex - inLeft; root.left build(preorder, preLeft 1, preLeft leftSize, inorder, inLeft, rootIndex - 1); root.right build(preorder, preLeft leftSize 1, preRight, inorder, rootIndex 1, inRight); return root; } }递归出口的判断用的是preLeft preRight。可能有同学会好奇为什么不用判断中序区间原因是前序和中序描述的是同一棵子树左右子树节点数相等前序区间和中序区间会同时为空。只要前序区间为空中序区间也一定为空所以只检查一个就够了。当然写上inLeft inRight也无妨代码会稍显冗余但更明确。2.4 这道题的易错点与面试加分点我复盘了网上常见的错误解法总结出三个高频翻车点第一区间下标算错。最常见的是把左子树前序区间的右边界写成preLeft rootIndex。这里必须清醒rootIndex是中序数组的下标不能直接拿去当前序数组的偏移量用。我自己的习惯是永远先写int leftSize rootIndex - inLeft;再推导前序区间这样能有效避免下标串门。第二递归出口判断失误。如果出口写成if (preLeft preRight)那么遇到只有一个节点的子树时会把左右孩子都置空逻辑上也能跑通但代码会多一层无意义的递归调用而且漏掉了preLeft preRight这种情况会导致数组越界。所以最好的写法仍然是判断稳健且语义清晰。第三题目给的值不保证互不相同。力扣这题默认节点值唯一但有些变种题会包含重复值这时 HashMap 直接存下标就行不通了。遇到重复值场景一般需要在 HashMap 中存一个下标列表再配合递归时传入的中序边界来选择落在当前区间内的那个下标。这是面试中常见的延伸追问你可以提前想一下应对思路。面试时如果想拿加分可以在讲完基本解法后主动补充一句这里还有一个细节——前序序列的第一个元素是根节点这个性质反过来也成立所以同理可证后序序列的最后一个元素也是根节点。如果题目给的是中序后序思路完全一样只是把根从前序头部换到后序尾部。3. 路径总和III从双重递归到前缀和优化3.1 题目在问什么路径的起点不需要是根节点先明确题目定义给定一棵二叉树和一个目标值targetSum要求统计有多少条路径的节点值之和等于targetSum。这里的路径必须从上往下也就是说路径上的每个节点必须是下一个节点的父节点或祖先节点。但路径的起点不一定是根节点终点也不一定是叶子节点。这个起点任意的条件是整道题的关键。如果路径必须从根节点出发那就是常规的根到叶路径和问题DFS 一遍就能解决。但这里路径可以从任意节点开始导致一个朴素思路是枚举每个节点作为起点然后向下累加找等于targetSum的路径。3.2 朴素双重递归思路简单但复杂度不理想最容易想到的解法是两层递归外层递归枚举每个节点作为路径起点内层递归从这个起点向下累加节点值统计有多少条路径和等于targetSum。class Solution { public int pathSum(TreeNode root, int targetSum) { if (root null) { return 0; } int count countFromNode(root, targetSum); count pathSum(root.left, targetSum); count pathSum(root.right, targetSum); return count; } private int countFromNode(TreeNode node, long targetSum) { if (node null) { return 0; } int count 0; if (node.val targetSum) { count; } count countFromNode(node.left, targetSum - node.val); count countFromNode(node.right, targetSum - node.val); return count; } }这段代码思路直白也很好写但问题在于时间复杂度是 O(n²)——每个节点都要做一次从它开始的深度遍历。当树退化成一条链时n 个节点每个都要向下走 O(n) 步总的操作次数就是 O(n²)。在力扣上这个解法遇到极端数据会超时所以只能作为理解题意的入门写法真正的标准解法是前缀和。3.3 前缀和思想把子数组和搬到树上如果你刷过数组相关的题目对前缀和 HashMap应该不陌生。经典的和为 K 的子数组就是维护一个前缀和 Map统计curSum - k出现的次数。路径总和III 本质上就是这个问题的树形版。树上的路径是单向向下的从根到某个节点的路径和可以看作树上的前缀和。那么一条从任意节点 A 到任意节点 B 的路径如果它的和为targetSum就等价于从根到 B 的路径和curSum减去从根到 A 的父节点的路径和prevSum差值等于targetSum。换句话说我们只需要统计在当前路径上有多少个历史前缀和等于curSum - targetSum。用 HashMap 存储前缀和 → 出现次数即可。每走一个节点更新当前前缀和然后查一下 Map 里curSum - targetSum出现的次数累加到答案中。这里有一个非常重要的细节Map 中存的必须是当前路径上的历史前缀和不能是整棵树别处的。所以当一棵子树递归完成、返回父节点时必须把当前节点的前缀和从 Map 中移除否则同一路径之外的前缀和会被错误统计。这个回溯时回滚的操作是这道题能否写对的关键。3.4 完整实现与关键的 long 类型细节先给完整代码然后说几个我实际踩过的坑class Solution { private int count 0; public int pathSum(TreeNode root, int targetSum) { MapLong, Integer prefixSumCount new HashMap(); prefixSumCount.put(0L, 1); dfs(root, 0L, targetSum, prefixSumCount); return count; } private void dfs(TreeNode node, long curSum, int targetSum, MapLong, Integer prefixSumCount) { if (node null) { return; } curSum node.val; count prefixSumCount.getOrDefault(curSum - targetSum, 0); prefixSumCount.put(curSum, prefixSumCount.getOrDefault(curSum, 0) 1); dfs(node.left, curSum, targetSum, prefixSumCount); dfs(node.right, curSum, targetSum, prefixSumCount); prefixSumCount.put(curSum, prefixSumCount.get(curSum) - 1); if (prefixSumCount.get(curSum) 0) { prefixSumCount.remove(curSum); } } }第一个坑是int 溢出。curSum随着遍历深度累加如果树很深且节点值较大curSum可能超出int范围。更隐蔽的是curSum - targetSum也可能溢出。所以我从一开始就用long来存前缀和。这是 LeetCode 测试用例里专门埋的坑很多人用int也能过大部分样例但遇到刻意构造的大数用例就会 WA而且怎么查都查不出原因。第二个坑是初始值0L - 1。这一行很多人不理解。它的含义是空前缀出现的次数为 1。也就是说如果从根节点出发到当前节点的整条路径和刚好等于targetSum那么curSum - targetSum 0此时需要能查到 0 的计数。不加这一行根节点到当前节点的整段路径永远统计不到。第三个坑是回滚时不能直接remove(curSum)。当前节点的前缀和在 Map 中的计数可能是 1也可能大于 1因为不同位置的节点可能出现相同前缀和。如果你直接remove假设这个前缀和在另一条路径上还出现了就会破坏 HashMap 的计数准确性。正确做法是先把计数减 1减到 0 再remove。我一开始没注意这个问题导致个别用例统计多了排查了半天。这道题讲完可以顺带提一下衍生版本力扣 437 还有一道变种路径总和III 的二叉树版本只统计向下路径而字节面试中出现过统计任意两点之间路径和为 K 的数量可以向上的版本那个需要换一种做法类似树的点分治或树上差分这里先不展开但如果你面试遇到可以往这个方向思考。4. 二叉树的最近公共祖先后序回溯的经典场景4.1 先理解题目定义与朴素想法题目定义给定一棵二叉树和两个节点 p、q找到它们最近的公共祖先。注意这里是二叉树而不是二叉搜索树所以不能用节点值的大小关系来剪枝只能从结构上找。关于最近公共祖先有一个容易混淆的边界如果一个节点本身就是 p 或 q那么它也可以作为自己的祖先。也就是说如果 p 是 q 的祖先那么答案就是 p 本身。这一点必须明确否则代码里的某些判断你会觉得多余。一开始我拿到这道题第一反应是从根节点出发分别找到从根到 p、从根到 q 的两条路径路径最后一个相同的节点就是答案。这个思路很朴素也很好理解需要两次遍历一次对比时间复杂度 O(n) 空间 O(h)。但面试时这个写法有个问题需要额外的数据结构保存路径代码量偏大而且一旦树的深度大路径列表的空间开销也不小。标准解法用后序回溯可以做到只用一个递归函数空间 O(h)递归栈本身思路也更优雅。4.2 后序回溯自底向上找公共祖先后序回溯的思路很巧妙一句话总结是从下往上看看每个节点的左右子树中是否包含了 p 和 q如果左子树有一个、右子树有一个那么这个节点就是最近的公共祖先。这里的关键是递归函数的返回值应该怎么设计。我采用如下约定lowestCommonAncestor(root, p, q)返回在这棵子树中能找到的 p 或 q 的最近公共祖先如果只找到了 p 或 q 本身就返回找到的那个节点如果都没找到返回 null。基于这个约定代码只有三种情况当前节点是 p 或 q直接返回当前节点。左子树返回非空、右子树返回非空说明 p 和 q 分别位于当前节点的左右两侧当前节点就是最近公共祖先。只有一侧返回非空说明 p 和 q 都在那一边返回那一边的结果即可。看代码class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null || root p || root q) { return root; } TreeNode left lowestCommonAncestor(root.left, p, q); TreeNode right lowestCommonAncestor(root.right, p, q); if (left ! null right ! null) { return root; } return left ! null ? left : right; } }这段代码只有十行左右但信息量很大。我分几个点讲清楚。第一个点是入口判断root p || root q的作用。这一行同时承担了两个职责一是如果当前节点就是目标节点直接返回实现了节点可以作为自身祖先的边界二是如果当前节点为空返回空。把这两个判断合在一起写代码非常精简也是这道题面试时的标准写法。第二个点是理解返回值的语义。递归返回的节点本质上是这棵子树中 p 或 q 的最近公共祖先或 p / q 本身。当左子树返回非空且右子树返回非空时说明在当前节点的左子树里找到了 p或 q右子树里找到了另一个p 和 q 被当前节点分开了所以当前节点是答案。当只有一侧非空时说明两个目标节点都在那侧答案也在那侧往上返回即可。第三个点是后序执行的时机。程序先递归处理左右子树再在返回后进行判断这就是后序决策模式。它天然地自底向上工作最底层的叶子节点最先被判断然后逐层向上直到某个祖先节点的左右子树分别包含 p 和 q。4.3 一个帮助理解的例子我拿一个具体例子走一遍递归过程这样比干讲要直观得多。假设有一棵树3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4要找 p 5q 4 的最近公共祖先。从根节点 3 开始递归左子树5再递归右子树1。右子树节点 1 的左右子树只有 0 和 8都不包含 5 或 4最终返回 null。左子树节点 5 的左右子树是 6 和 2。6 不包含目标节点返回 null节点 2 的右子树是节点 4而节点 4 就是 q所以节点 4 返回自身节点 2 的右子树返回 4左子树节点 7 返回 null于是节点 2 的返回结果是 4。节点 5 的左子树返回 null右子树返回 4所以节点 5 把 4 继续向上返回。根节点 3 的左子树返回了 5也就是 p 本身右子树返回了 null于是根节点返回 5。最终答案是 5。这个例子也很好地展示了p 是 q 的祖先p 可以作为自身的公共祖先这一边界。我在面试时喜欢主动把这个例子讲一遍因为大多数面试官看到你能手推一个完整递归过程基本就会认定你是真的理解了而不是背的模板。4.4 这道题在面试中的延伸问法最近公共祖先这道题在面试中出现的频率非常高而且很多人会接着往下问变种。第一个变种是二叉搜索树版本。由于 BST 有大小关系可以利用节点值比较来剪枝如果 p 和 q 的值都小于当前节点去左子树找都大于当前节点去右子树找一大一小则当前节点就是答案。这个版本也用递归但思路完全不同如果面试官从二叉树版本追问 BST 版本属于常规操作。第二个变种是如果每个节点有父指针。这时问题退化为两个链表求交点先让深度大的节点向上走到和另一个节点同一深度再同步向上走第一次相等的节点就是答案。这是常见的追问因为从树的问题变成了链表问题考察知识迁移能力。第三个变种是多次查询。如果在一棵固定的树上频繁询问不同节点对的最近公共祖先每次递归 O(n) 就不现实了。这时候一般用 Tarjan 离线算法或 ST 表做在线查询先说思路即可面试很少要求现场实现。我个人的经验是二叉树本身写出递归不难难的是在递归过程中讲清楚为什么这么写是对的。建议你在刷最近公共祖先这道题时不要只满足于 AC而是练给自己讲一遍完整的递归流程。能做到这一点这道题才算真正吃透了。5. 二叉树中的最大路径和负数截断与贡献值思维5.1 题目定义与常见的理解误区二叉树中的最大路径和题目定义是一条路径从一个节点出发沿着父子连接走到另一个节点路径至少包含一个节点求所有可能路径的最大和。这里的路径不要求经过根节点也不一定是从上往下的可以是从某个节点向上再向下拐弯。这个定义导致了三个理解误区我刷题时全踩过误区一以为路径必须经过根节点。如果必须经过根节点那问题就退化成根到任意叶节点的最大路径和一遍 DFS 就能解决。但题目明确说任意节点到任意节点所以答案可能在某个子树的内部路径上与根毫无关系。误区二以为路径必须从上到下。这题的路径可以拐弯比如先从左子树向上走到某个节点再向下走进右子树形成一个倒 V形。这一点和路径总和III 的只向下完全不同。误区三以为返回值就是答案。这道题的递归函数返回值并不是以当前节点为顶点的最大路径和的最终答案而是经过当前节点、且只能拐一次弯的最大贡献值。这个区别极其关键直接决定了能不能写对。5.2 核心思维每个节点只贡献一条单侧最大路径为了说清楚我先引入一个概念——贡献值。定义dfs(node)的返回值是以node为起点向下走到任意一个节点能够得到的最大路径和且这条路是单侧的要么一直往左走要么一直往右走不能拐弯。这相当于从 node 出发向下延伸能提供的最大正能量。基于这个概念对于当前节点node可能的最大路径只有两种形态第一种路径以node为最高点拐弯点从左子树上来、经过node、再下去到右子树。这条路径的和是左贡献 node.val 右贡献。这就是需要在递归过程中更新全局答案的候选值。第二种路径只是从node向下延伸的单侧路径它不是最终答案而是要返回给父节点使用的贡献值。它的值是max(左贡献, 右贡献) node.val取较大的那一侧。这两个形态很容易混淆它们的区别是全局答案可以拐弯返回值不能拐弯。如果返回值也随便拐弯父节点在拼接路径时就会出现路径被重复使用的错误。5.3 负数截断为什么贡献值要和 0 取最大值接下来的关键问题是如果某一侧的贡献值是负数怎么办假设节点右子树的贡献值是 -5而左子树贡献值是 10那么经过当前节点、经过右子树的路径和是10 node.val - 5这比不经过右子树的路径和10 node.val更小。显然负数贡献在拼接路径时只会拉低总和与之无关。所以当计算父节点需要的单侧贡献时负数贡献就应该直接视为 0表示我宁可不走这条路。落实到代码上就是进入递归时直接截断int left Math.max(0, dfs(node.left)); int right Math.max(0, dfs(node.right));这个Math.max(0, ...)是整道题的精髓。它既保证了向上返回的贡献值不会因为负数而拖累父节点也保证了求全局答案时负数分支不会进入候选计算。如果没有这一行遇到节点值全为负数的树答案会变成负数总和而不是最大的那个负数直接 WA。5.4 完整实现与全局变量的更新时机给出完整代码class Solution { private int maxSum Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return maxSum; } private int dfs(TreeNode node) { if (node null) { return 0; } int leftGain Math.max(0, dfs(node.left)); int rightGain Math.max(0, dfs(node.right)); int curPathSum leftGain rightGain node.val; maxSum Math.max(maxSum, curPathSum); return Math.max(leftGain, rightGain) node.val; } }几个细节值得单独说明。第一为什么maxSum初始化为Integer.MIN_VALUE而不是 0因为节点的值可能全是负数如果初始化为 0当树中所有路径和都是负数时答案会被错误地算成 0。只有极小值才保证第一个候选值一定会更新全局变量。这是一个容易忽略的边界。第二为什么返回时用Math.max(leftGain, rightGain)而不是都加上因为返回给父节点的贡献值只能选择一侧路径不能分叉。如果左右都加回到父节点后这个分支路径就无法继续向上拼接了——路径会变成三叉不符合定义。第三全局答案的更新位置。它在后序位置也就是拿到左右贡献值之后。这个位置保证了每一棵子树内部的拐弯路径都被考虑过不需要额外枚举路径的最高点。自底向上每个节点都有机会作为路径最高点被计入候选所以最终答案不会漏掉任意一条路径。这道题从思路上其实是这几道里最难的一题但代码写出来反而最短。面试时如果让我给二叉树递归的含金量排序我会把最大路径和排在第一因为它最能区分背模板的人和理解递归本质的人。5.5 与树的直径的对比加深对返回值设计的理解最后说一个很好的对比题——二叉树的直径力扣 543。那题要求最长的路径边数允许拐弯但节点值没有正负之分每个节点只能提供 1 或 0 的贡献。直径的递归写法是class Solution { int max 0; public int diameterOfBinaryTree(TreeNode root) { depth(root); return max; } private int depth(TreeNode node) { if (node null) return 0; int left depth(node.left); int right depth(node.right); max Math.max(max, left right); return Math.max(left, right) 1; } }你看直径的返回值和最大路径和的返回值结构完全一样都返回单侧最长全局答案都在拼接左右两侧时更新。区别只是直径用left right统计边数最大路径和用leftGain rightGain node.val统计数值和直径没有负数截断最大路径和必须Math.max(0, ...)。把这两道题放在一起对比着刷你会对后序收集模式理解得非常透彻。以后再遇到类似的题比如求树中最长同值路径基本上拿到手就能想清楚递归返回什么、答案在哪里更新。6. 四道题横向对照与刷题建议6.1 核心考点与复杂度速查这篇的四道题我整理了一张速查表每次面试前扫一眼能快速唤回记忆题目核心考点递归模式时间复杂度空间复杂度关键代码特征从前序与中序遍历构造二叉树分治构建、区间边界推导前序构建O(n)O(n)HashMap 预处理中序下标路径总和III前缀和、HashMap 回溯前序累加后序回滚O(n)O(n)curSum 用 long 防溢出二叉树的最近公共祖先后序回溯、自底向上后序决策O(n)O(h)left/right 返回值分情况二叉树中的最大路径和贡献值设计、负数截断后序收集O(n)O(h)Math.max(0, dfs(...))空

递归分治与后序决策：二叉树四道高频难题全解析

相关推荐

高通5G 3GPP Release-18解读：AI/ML空口、NTN与RedCap的落地验证指南

AI日报自动化生成实战：从信息洪流到结构化认知的筛选与写作流程

Ant Design Blazor Segmented 组件自定义渲染：用 ChildContent 打造富内容分段控制器

更多资讯

Sherpa-onnx 跑 Zipformer ONNX 推理：3 步绕开 Required inputs missing

AI日报制作全流程：从信源分层到自动化抓取与人工筛选

.NET接入钉钉开放平台实战：从Token缓存到事件订阅

fpinscala 第 11 章练习 20 解答：从零实现只读环境 Reader Monad

YOLO垃圾四分类数据集制作全指南：从标注到验收的工程实践

XQuad 编译指南：读懂 `problem.compile()` 生成的 encoder / verifier / decoder 三份 XQASM

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？