2月23日这天我给自己安排的是LeetCode 97到99这三道中等题。说实话刚开始纯属按编号顺手点进来的等三道题都啃完才发现这居然是一组绝佳的组合拳一道字符串动态规划一道二叉树遍历一道二叉树遍历的进阶变体把两个最常考的数据结构场景都覆盖到了。如果你最近正在集中刷二叉树和二维DP又或者面试前想找几道有区分度的题练手这三道题非常值得放在一起过一遍。先说结论97题交错字符串考的是二维DP的状态设计98题验证二叉搜索树考的是对BST定义的理解深度99题恢复二叉搜索树则是98题的强化版要求你在中序遍历的过程里找出两个“错位”的节点。三道题难度都在中等但每一道都有不止一个坑尤其是99题如果面试官追问“能不能不用递归也不用栈”那就是在考Morris遍历了。下面我把当天的完整思路、代码和踩坑记录都整理出来。1. 三道题放在一起刷思路是这么串起来的1.1 选题原因与题目难度定位这三道题放在同一天刷不是巧合。从题目编号看它们挨着从知识点看它们正好互补97题是字符串类的二维动态规划训练的是“状态定义”和“状态转移”98题是二叉树的中序遍历与递归边界控制99题同样是二叉树但考察点从“判断”升级成了“修复”对遍历过程的理解要求更高。把这三题串联起来等于用一个晚上把两个高频考点的几种典型问法都过了一遍。难度方面三题都是中等。但我的实际体验是97题如果没见过类似题想清楚dp数组含义会卡一会儿98题很多人会写错因为直觉解法只比较了父节点和直接子节点忽略了整棵子树的约束99题如果不要求O(1)空间其实不难难的是“不允许用额外数组记录中序序列”这个限制。所以整体消耗时间大概是97题四十分钟98题二十分钟99题一个小时总计两个多小时。如果你一次刷不完拆成两天也没问题但建议一定按这个顺序。1.2 三题共用的核心数据结构与算法套路先拆开看这三题背后的公共套路。97题表面上在讲字符串实际上它的状态转移很像“路径选择”s3的每一个字符要么来自s1要么来自s2你需要在两个来源之间做决策。这跟编辑距离、最长公共子序列是同一类问题核心是“当前状态由前一个状态决定而前一个状态可能有多种转移来源”。98题和99题都是二叉树中序遍历的经典应用。二叉搜索树的一个重要性质就是中序遍历结果严格递增所以“验证BST”等价于“验证中序序列严格递增”“恢复BST”等价于“在中序序列里找到两个交换位置的元素并换回来”。这两道题放在一起你会发现一个通用套路遇到BST相关问题先想中序遍历很多时候比硬套递归定义更简单。这种“用同一种遍历解决两个互为镜像的问题”的安排是我比较推荐的自学方式。单独刷一道题你记住的只是一个解法把关联题放在一起刷你记住的是一种“题目之间的映射关系”。比如刷完98题再刷99题你会自然而然想到“验证”和“恢复”不过是有序性的两个方向。2. 第97题交错字符串的动态规划拆解2.1 题目理解与第一直觉97题的题干是给定三个字符串s1、s2、s3判断s3是否由s1和s2交错组成。所谓交错就是保持s1和s2各自字符的相对顺序不变然后把它们穿插起来。举个例子s1 aabccs2 dbbcas3 aadbbcbcac结果是true如果s3变成aadbbbaccc就是false。我第一次看到这题第一反应是双指针同时遍历s1和s2遇到s3当前字符匹配哪个就走哪个。但这个思路很快就会被反例打脸因为当s3的当前字符同时能匹配s1和s2的当前字符时你选哪条路直接决定后续是否可行而双指针做不了“回溯”。这说明什么呢说明这类“多选一”的路径决策问题天然适合用动态规划因为DP本质上就是在枚举所有可能的决策组合而不是一条路走到黑。2.2 DP状态定义与转移方程推导定义dp[i][j]表示s1的前i个字符和s2的前j个字符能否交错组成s3的前ij个字符。这个定义的关键在于不用关心s3剩下的部分怎么组成只关心当前这两个前缀能不能“拼出”s3对应长度的前缀把大问题切成小问题。状态转移分两种情况。第一种情况s3的第ij个字符也就是当前拼出来的最后一个字符来自s1那么前提是s1[i-1]等于s3[ij-1]并且dp[i-1][j]为true第二种情况最后字符来自s2那么前提是s2[j-1]等于s3[ij-1]并且dp[i][j-1]为true。两种情况只要有一种成立dp[i][j]就是true。用伪代码表示就是dp[i][j] (dp[i-1][j] and s1[i-1] s3[ij-1]) or (dp[i][j-1] and s2[j-1] s3[ij-1])初始条件也要想清楚。dp[0][0]表示两个空串能拼出空串为true。dp[i][0]只依赖s1连续匹配s3dp[0][j]只依赖s2连续匹配s3。这些都是“退化情况”很多bug就出在这里后面我会专门讲。2.3 一维滚动数组优化与代码实现二维dp数组是(m1)乘(n1)空间O(mn)。但观察转移方程可以发现dp[i][j]只依赖dp[i-1][j]上一行同一列和dp[i][j-1]当前行前一列所以可以用一维数组滚动更新空间降到O(n)。这里有个细节因为要用到“当前行前一列”的值内层循环j必须从左往右遍历同时dp[j]在更新前保留的是“上一行第j列”的值正好可以作为dp[i-1][j]用。我当天写的最终代码如下def isInterleave(s1: str, s2: str, s3: str) - bool: m, n len(s1), len(s2) if m n ! len(s3): return False dp [False] * (n 1) for i in range(m 1): for j in range(n 1): if i 0 and j 0: dp[j] True elif i 0: dp[j] dp[j - 1] and s2[j - 1] s3[j - 1] elif j 0: dp[j] dp[j] and s1[i - 1] s3[i - 1] else: dp[j] (dp[j] and s1[i - 1] s3[i j - 1]) or (dp[j - 1] and s2[j - 1] s3[i j - 1]) return dp[n]还有一个小优化每次进入外层循环时可以先判断s3[ij-1]是否等于s1[i-1]或s2[j-1]如果两者都不等于直接返回false也能加速不过实测数据量不大收益有限。核心还是把状态定义和转移方程写对。3. 第98题验证二叉搜索树边界条件的重灾区3.1 常见的错误解法与分析98题要求判断一棵二叉树是不是有效的二叉搜索树。BST的定义是左子树所有节点的值小于根节点右子树所有节点的值大于根节点并且左右子树也必须是BST。我见过最多人踩的坑就是只比较“当前节点和它的直接左儿子、直接右儿子”写成类似下面这种if root.left and root.left.val root.val: return False if root.right and root.right.val root.val: return False return isValidBST(root.left) and isValidBST(root.right)这个写法错在把“根节点大于所有左子树节点”简化成了“根节点大于左儿子”。考虑这样一棵树根是10左儿子是5左儿子的右儿子是15。按照上面的代码5小于10、15大于5每一层都满足但它不是BST因为15在左子树里却大于10。这种错误特别隐蔽因为用几棵简单测试树根本测不出来。所以刷这道题一定要先想明白BST的约束是“全局”的不是“局部”的。每往左走一步根节点就变成一个新的上界每往右走一步根节点就变成一个新的下界。这个“上下界传递”的思路是解这道题的核心。3.2 递归上下界法的正确姿势正确的递归做法是给每个节点传一个允许的取值范围。根节点的范围是负无穷到正无穷往左子树走的时候上界更新为当前节点值下界不变往右子树走的时候下界更新为当前节点值上界不变。任何一个节点的值超出这个范围就返回false。代码可以这样写def isValidBST(root): def helper(node, low, high): if not node: return True if low is not None and node.val low: return False if high is not None and node.val high: return False return helper(node.left, low, node.val) and helper(node.right, node.val, high) return helper(root, None, None)这里用None而不是float(-inf)是为了避免节点值正好等于边界时产生误判。比如题目允许节点值等于int的最小值如果用float(-inf)和int比较精度没问题但如果用-2**63这类硬编码就会有风险。用None表示“没有限制”是最稳的。3.3 中序遍历判有序法及两种写法对比除了递归上下界还可以用中序遍历。因为BST的中序遍历结果是严格递增的所以只要在中序遍历过程中检查当前节点值是否比前一个节点值大即可。中序遍历有两种实现递归和显式栈。递归代码简单但面试时如果树很深递归栈会占用O(h)空间显式栈同样是O(h)空间但不会爆系统栈。def isValidBST(root): stack, inorder [], None while stack or root: while root: stack.append(root) root root.left root stack.pop() if inorder is not None and root.val inorder: return False inorder root.val root root.right return True对比一下两种方法递归上下界法更贴近BST的定义适合在思维层面解释中序遍历法更贴近“有序数组”这个性质适合在代码层面快速实现。两种的时间复杂度都是O(n)空间最坏都是O(n)。我建议两个都掌握因为99题会用到中序遍历的思路而很多面试官喜欢先让写递归上下界再追问“有没有别的做法”。4. 第99题恢复二叉搜索树从O(n)到O(1)空间4.1 中序遍历找逆序对的完整思路99题说BST中恰好有两个节点的值被错误交换了要求找出这两个节点并恢复而且进阶要求是空间复杂度O(1)。这题的关键洞察是既然BST中序遍历是升序的那么交换两个节点后中序序列里必然会出现“降序对”。找到这两个降序对就能反推出被交换的两个节点。先模拟一下。假设正确的序列是[1, 2, 3, 4, 5, 6, 7]交换2和6后变成[1, 6, 3, 4, 5, 2, 7]。遍历时第一次发现6大于3这是一个降序对那么被交换的节点中较大的那个6是第一个节点继续往后走第二次发现5大于2另一个降序对较小的那个2是第二个节点。把6和2交换回去就恢复了。还有一种特殊情况如果交换的是相邻两个节点比如[1, 3, 2, 4, 5]整个序列只会出现一次降序对3大于2。这时被交换的两个节点就是3和2。所以算法统一处理方式是记录第一个降序对的第一个节点以及最后一个降序对的第二个节点最后交换它们。代码里用两次判断第一次降序记录first和second之后每次遇到降序只更新second。4.2 相邻交换与不相邻交换的区别这里有一个容易忽略的细节相邻交换和不相邻交换处理方式不一样。不相邻交换会在中序序列里产生两个降序对相邻交换只产生一个。但上面的算法统一处理了两者单降序对时first是较大的那个节点second是较小的那个双降序对时first取第一个降序对的较大节点second取第二个降序对的较小节点。有的实现会写成“遇到第一个降序对就记录first和second遇到第二个降序对只更新second”这样能覆盖两种场景。我最初写的时候习惯只记录第一个降序对的两个节点结果在不相邻交换的用例上报错。后来才意识到first要取第一个降序对的第一个节点second要取第二个降序对的第二个节点而不是第一个降序对的第二个节点。这个细节不跑几个用例光靠脑子想真的容易错。4.3 Morris遍历实现真正的O(1)空间如果用递归或显式栈做中序遍历空间复杂度是O(h)最坏情况下树退化成长链时是O(n)不满足进阶要求。真正O(1)空间的方案是Morris遍历。Morris遍历的核心思想是利用叶子节点的空闲指针把中序遍历的前驱节点指向当前节点形成一个临时线索方便回溯。当天我写的版本比较长拆开解释def recoverTree(root): first second prev None cur root while cur: if not cur.left: # 没有左子树直接访问当前节点 if prev and cur.val prev.val: if not first: first prev second cur prev cur cur cur.right else: # 找当前节点的左子树的最右节点中序前驱 predecessor cur.left while predecessor.right and predecessor.right ! cur: predecessor predecessor.right if not predecessor.right: # 建立线索 predecessor.right cur cur cur.left else: # 线索已存在说明左子树已经遍历完访问当前节点并断开线索 predecessor.right None if prev and cur.val prev.val: if not first: first prev second cur prev cur cur cur.right first.val, second.val second.val, first.val个人建议90%的场景下先用显式栈版本把逻辑写对面试官追问优化时再写Morris。因为Morris遍历的指针操作比较多一上来就写很容易把自己绕晕。我当天是先用栈版本通过再专门推演了一遍Morris才在编辑器里重新敲了一遍。5. 实操过程复盘与三题串联总结5.1 三道题的时间复杂度与空间复杂度对照当天刷完我把三题的复杂度整理成了一个表方便后续复习题号核心解法时间复杂度空间复杂度关键优化97 交错字符串二维动态规划O(m*n)O(m*n)可优化为O(n)一维滚动数组98 验证二叉搜索树递归上下界 / 中序遍历O(n)最坏O(n)None表示无界99 恢复二叉搜索树中序遍历找逆序对O(n)O(h)可优化为O(1)Morris遍历这个表看起来简单但每次复习都能快速唤醒记忆。尤其是97题如果不做滚动数组优化在m和n都接近1000时dp数组会占约1MB内存虽然不算夸张但面试时主动做优化绝对是加分项。5.2 刷题时的通用判断套路刷完这三题我总结了一套“拿到题先判断类型”的思路。看到“判断是否可行”“有多少种方案”这类问题优先往DP方向想看到二叉树且涉及有序性优先往中序遍历方向想看到一个题是另一个题的“升级版”先想能不能复用基础题的结论。比如99题用到的中序有序性正是98题的核心性质这说明很多难题只是基础题换了一层外壳。我还发现一个值得养成的习惯每道题先想清楚“暴力解法”是什么再优化。97题的暴力是枚举所有交错路径98题的暴力是每个节点递归验证子树最大值最小值99题的暴力是拷贝中序序列到数组再排序比对。暴力解法能帮你看清问题的本质后面的优化只是减少重复计算或节省空间而已。6. 常见问题与排查技巧实录6.1 交错字符串DP的初始化陷阱97题最经典的报错场景是s3长度不等于s1加s2之和。这个判断一定要放在最前面否则后面ij会越界。还有一个隐藏的坑滚动数组里dp[j]在i0这一轮依赖dp[j-1]必须保证j从小到大遍历反过来如果依赖上一行同列的值这一维数组更新前存的就是旧值刚好能用。很多人在一维化时报错就是因为把j的遍历方向写反了。另外当s1或s2为空串时代码里“elif i 0”和“elif j 0”两个分支要能正确处理。我见过不少实现直接用统一转移方程硬套结果空串的用例直接数组越界。如果你觉得分支判断麻烦也可以给dp数组加一列哨兵把边界情况都塞进统一逻辑里。6.2 二叉搜索树边界值的处理98题和99题都会遇到节点值等于int边界的情况。我的建议是统一用None表示“无限制”不要用float(-inf)或float(inf)。因为有些题目的节点值是int最小值或最大值如果用float参与比较虽然Python里不会出错但如果你把代码迁移到强类型语言很容易出现精度或类型问题。把边界情况抽象成None语义也更清晰。99题还有一种常见错误只找到第一个降序对的两个节点就交换导致“不相邻交换”用例失败。排查方法很简单打印中序遍历结果人工看降序对的位置。比如序列是[1, 6, 3, 4, 5, 2, 7]你就知道需要交换的是6和2而不是6和3。这个排查习惯比盲改代码高效得多。6.3 Morris遍历断开线索的现场还原Morris遍历最容易出问题的地方是“线索断没断干净”。如果代码漏掉了predecessor.right None这一步树的右指针就会被改成线索导致后续遍历死循环或者结构损坏。我一般会画一个三节点的树手动模拟两轮循环检查每个节点的左右指针是否回到原始状态。现场还原的思路是建立线索时把前驱节点的右指针指向cur下次再经过这个前驱时通过判断right cur来知道左子树已经遍历完此时再断开线索并访问cur。如果面试时时间紧张也可以先和面试官确认“是否可以直接用O(h)空间”很多时候面试官接受栈解法O(1)空间的Morris是加分项而非必选项。我建议平时把Morris当成一种思维训练理解它在做什么但面试中优先保证栈解法写得又快又对。最后再分享一个小技巧三道题里最让我意外的是97题和99题从表面看毫无关系但它们都需要“记录多个前置状态”才能做出决策。97题记录的是两个字符串前缀的匹配状态99题记录的是遍历前驱节点的值。刷题刷多了你会发现所谓难题往往是基础题换个场景重新包装核心套路就那些关键在于你能不能识破那层包装。2月23日这组题帮我很好地巩固了这个认知。