LeetCode 97-99：动态规划与二叉搜索树中序遍历的进阶实战

2月23日我按计划把刷题打卡进度推进到LeetCode第97-99题。一天三道题听起来不算多但这一组的含金量非常在线第97题交错字符串是经典的双序列动态规划第98题验证二叉搜索树和第99题恢复二叉搜索树则是围绕BST中序遍历展开的一组递进式问题。如果你正在准备算法面试、转码复习或者只是想在一些核心知识点上保持手感这一组题值得认真过一遍。三道题分别是两个方向一个字符串DP两个二叉树。表面上没什么关联但它们恰好都适合在“基础模板”之上做优化——97题可以讲清楚滚动数组怎么省空间98题能把BST的“范围约束”讲透99题则是中序遍历的进阶应用甚至能延伸到Morris遍历。一次刷完等于把DP和树遍历两条主线都练到了。1. 今日题单概览与刷题思路1.1 97-99题分别考什么先把三题的基本信息摆出来方便对照题号难度题目核心考点建议掌握解法97中等Interleaving String 交错字符串双序列动态规划二维DP并优化为一维滚动数组98中等Validate Binary Search Tree 验证二叉搜索树BST性质、递归、中序遍历递归上下界 / 迭代中序递增判断99困难Recover Binary Search Tree 恢复二叉搜索树BST中序遍历、空间复杂度优化中序找逆序对、Morris遍历三题的难度阶梯也比较明显97题是常规的DP思路状态定义清楚了就完成一大半98题属于“看似简单但很容易写错”的二叉树题重点考细节99题是其中最难的一道很多人第一次做会卡在“怎么在O(1)空间下完成中序遍历”上。放在同一天刷刚好可以体会到同一类遍历技巧在不同难度下的应用。1.2 我为什么把这三题放在同一组刷题最忌讳零散今天一道链表、明天一道图论、后天一道贪心知识点之间没有关联记不牢。我选择把97-99放在同一天原因很简单它们能形成一条逻辑链条。第97题强调“状态定义”。双序列DP题的通用套路是定义dp[i][j]然后思考最后一个字符来自哪个序列。这个模板掌握之后后面遇到编辑距离、最长公共子序列、正则表达式匹配都会轻松很多。第98题和第99题则是一对“兄弟题”。前者要求判断一棵树是不是BST后者要求修复一棵不合法BST。两题共用中序遍历这个底层工具。中序遍历在BST中一定会输出递增序列所以98题靠这个性质检查99题靠这个性质找错。这样安排还有一个好处第二天复盘时不需要重新回忆上下文只要记住“97是一道字符串DP98和99是BST中序遍历的两次应用”整个题组的知识点就都能串起来。对正在准备面试的人来说这种成组记忆的效率比孤立的题目高很多。2. 97题交错字符串的动态规划解法2.1 先踩一遍双指针的坑先读题给三个字符串s1、s2、s3判断s3能否由s1和s2交错组成。所谓交错就是s1和s2内部的字符相对顺序都不能变但两个序列可以互相穿插。我第一反应是双指针p1指向s1p2指向s2遍历s3看当前字符匹配哪个指针就移动哪个。这个思路在“当前字符只可能匹配其中一个指针”的时候是有效的但问题在于当s3当前字符同时匹配s1和s2时你无法确定该走哪边。举个例子s1 abs2 aas3 aaba。如果双指针选择先匹配s2走到某个位置就会卡住最终误判为false。但实际上s3可以由s1和s2交错组成s3[0]来自s1的as3[1]来自s2的as3[2]来自s1的bs3[3]来自s2的a完全合法。这个例子说明双指针本质是“贪心”一旦遇到多个可选项它没有能力判断哪条路是对的。交错字符串需要的是“把每条路都试一遍“的能力这正是动态规划或者回溯加记忆化能提供的。2.2 状态定义和转移方程双序列DP的套路是先想清楚两个序列各自“走到了哪里”。这里用dp[i][j]表示s1的前i个字符和s2的前j个字符能不能交错组成s3的前ij个字符。初始状态是dp[0][0] true表示两个空字符串可以组成空字符串。第一行dp[0][j]表示只用s2的前j个字符去匹配s3前j个字符第一列dp[i][0]表示只用s1的前i个字符去匹配s3前i个字符。转移方程看s3的最后一个字符也就是s3.charAt(i j - 1)它可能来自两个地方要么来自s1的第i个字符此时需要s1.charAt(i - 1) s3.charAt(i j - 1)并且之前的dp[i-1][j]成立要么来自s2的第j个字符需要s2.charAt(j - 1) s3.charAt(i j - 1)并且之前的dp[i][j-1]成立。两个条件满足任意一个当前状态就成立。这个状态定义的关键点是s1和s2各自的字符顺序天然被“前缀”这个概念保护住了。dp[i][j]只表示前i个和前j个的匹配情况后面怎么穿插都不用管因为每一步都只考虑当前位置的字符归属。2.3 一维滚动数组的实现细节二维DP的时间复杂度和空间复杂度都是O(mn)。很多情况下m和n都能到几百甚至上千O(mn)空间还能接受但面试时如果能把它优化到O(n)空间会是明显的加分项。滚动数组的思路是观察dp[i][j]的转移只依赖上一行的dp[i-1][j]和同一行左边的dp[i][j-1]。因此可以只保留一行外层循环i从1到m内层循环j从1到n不断覆盖数组。这里有一个很容易踩的坑内层循环j只能正序遍历不能倒序。原因在于dp[j-1]需要是“当前行已经更新过的值”正序更新能保证左边的新值被用到而dp[j]在被覆盖前仍然是上一行的旧值正好是转移方程里需要的dp[i-1][j]。参考实现如下class Solution { public boolean isInterleave(String s1, String s2, String s3) { int m s1.length(), n s2.length(); if (m n ! s3.length()) { return false; } boolean[] dp new boolean[n 1]; dp[0] true; // 初始化第一行只使用 s2 for (int j 1; j n; j) { dp[j] dp[j - 1] s2.charAt(j - 1) s3.charAt(j - 1); } for (int i 1; i m; i) { // 更新第一列只使用 s1 dp[0] dp[0] s1.charAt(i - 1) s3.charAt(i - 1); for (int j 1; j n; j) { dp[j] (dp[j] s1.charAt(i - 1) s3.charAt(i j - 1)) || (dp[j - 1] s2.charAt(j - 1) s3.charAt(i j - 1)); } } return dp[n]; } }注意把二维数组优化成一维时不要把方向搞反。依赖左侧状态时正序更新依赖上方状态时需要保留旧值这里正序恰好两全其美。如果改成倒序dp[j-1]变成了上一行的值整个状态推导就错了。3. 98题验证二叉搜索树的关键是“范围”3.1 递归上下界不要只比较父子节点验证BST的条件是对任意节点左子树所有节点的值都小于该节点右子树所有节点的值都大于该节点。很多初学者会写成判断node.left.val node.val node.right.val node.val然后递归左右子树。这个写法看着合理其实有问题。比如下面这棵树根节点5左孩子33的右孩子是6。单看每个局部关系都满足“左小右大”但6出现在根节点5的左子树里已经违反了BST定义。正确思路是给每个节点传一个“允许范围”。进入左子树时范围变为(当前下界, 当前节点值)进入右子树时范围变为(当前节点值, 当前上界)。节点值必须落在开区间内。Java实现class Solution { public boolean isValidBST(TreeNode root) { return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean validate(TreeNode node, long lo, long hi) { if (node null) { return true; } if (node.val lo || node.val hi) { return false; } return validate(node.left, lo, node.val) validate(node.right, node.val, hi); } }注意初始边界我用了Long.MIN_VALUE和Long.MAX_VALUE而不是Integer.MIN_VALUE和Integer.MAX_VALUE。因为二叉树节点的值本身可以是Integer.MIN_VALUE如果你用它做初始下界第一次判断就会出现node.val lo把合法节点误判掉。3.2 中序遍历的递增判断BST还有一个等价性质中序遍历的结果必须严格递增。所以另一种解法是直接做中序遍历每访问一个节点都检查它是否大于前一个被访问节点。用迭代栈实现可以避免递归深度过大也更好表现“边遍历边判断”的结构class Solution: def isValidBST(self, root: TreeNode) - bool: stack [] prev None while stack or root: while root: stack.append(root) root root.left root stack.pop() if prev is not None and root.val prev: return False prev root.val root root.right return True这里有一个细节判断条件是root.val prev不是。BST要求严格递增相等值同样不合法。我在实际刷题中见过不少人写成小于号导致重复值也能通过判断这在普通测试用例里不容易暴露一旦遇到[2,2]这样的输入就会翻车。3.3 容易被忽略的边界条件空树和单节点树都属于合法BST递归实现里node null返回true迭代实现里栈空自然退出都覆盖到了。但这题真正的坑有两个。第一个是初始边界类型。如果使用int边界一旦节点值等于Integer.MIN_VALUE或Integer.MAX_VALUE判断就会出错。使用long类型或Python的float(-inf)都能避开。第二个是递归深度。如果输入是一棵极度失衡的树比如所有节点只有左孩子递归深度会达到节点数容易栈溢出。这时候迭代中序是更稳的方案。面试时建议两种方法都能写先答递归版再补充迭代版显得思路完整。4. 99题恢复二叉搜索树的三种解法4.1 逆序对就是突破口这道题给一棵“合法BST中恰好有两个节点被错误交换”的树要求恢复。核心思路仍然是中序遍历但和98题不同的是要把破坏点找出来并修正。中序遍历一个合法BST得到的是严格递增序列。如果两个节点被交换序列会出现一至两处逆序。比如原序列[1,2,3,4,5]交换2和5后变成[1,5,3,4,2]可以看到两处逆序(5,3)和(4,2)。找法很简单在中序遍历过程中记录上一个访问的节点last。一旦last.val current.val说明顺序被破坏了。第一次发现逆序时把last记为first把current记为second后面再发现逆序时只更新second为当前节点。遍历结束后交换first和second的值。为什么第二次发现逆序时只更新second因为第一次逆序的last才是被换错的较大节点而真正需要和它交换的是最后一次逆序里的current。如果只有一处逆序说明被交换的两个节点在中序序列里是相邻的此时second就是当前current。4.2 递归和栈版本的实现先看用递归中序实现的版本。关键在于维护三个成员变量first、second、last。每次访问当前节点时都和上一个节点比较。Java代码class Solution { private TreeNode first null; private TreeNode second null; private TreeNode last null; public void recoverTree(TreeNode root) { inorder(root); int temp first.val; first.val second.val; second.val temp; } private void inorder(TreeNode root) { if (root null) { return; } inorder(root.left); if (last ! null last.val root.val) { if (first null) { first last; } second root; } last root; inorder(root.right); } }这里有个非常容易出错的地方second的赋值一定要放在if (first null)判断外面。也就是不管是不是第一次发现逆序second都要更新为当前节点。如果只在first null时设置second遇到两处逆序的场景second就会停在第一处逆序的current上最终交换错误。迭代栈版本只是在遍历方式上换成了显式栈找逆序对和交换逻辑完全一样。一般面试先写递归版本再补充栈版本即可。4.3 Morris遍历做到O(1)空间递归和栈的空间复杂度都是O(H)H是树高。最坏情况下树退化成链表空间是O(n)。如果面试官要求“用O(1)空间实现”就需要上Morris遍历。Morris遍历的核心思想是利用叶子节点的空指针把当前节点接到左子树最右节点的右指针上形成临时线索。这样不需要栈也能回到当前节点遍历结束后再把线索断开恢复原树结构。Java实现class Solution { public void recoverTree(TreeNode root) { TreeNode first null; TreeNode second null; TreeNode last null; TreeNode cur root; while (cur ! null) { if (cur.left null) { // 访问 cur if (last ! null last.val cur.val) { if (first null) { first last; } second cur; } last cur; cur cur.right; } else { TreeNode predecessor cur.left; while (predecessor.right ! null predecessor.right ! cur) { predecessor predecessor.right; } if (predecessor.right null) { // 建立线索 predecessor.right cur; cur cur.left; } else { // 左子树遍历完成断开线索并访问 cur predecessor.right null; if (last ! null last.val cur.val) { if (first null) { first last; } second cur; } last cur; cur cur.right; } } } int temp first.val; first.val second.val; second.val temp; } }Morris遍历需要注意两个地方。一是“建立线索”的阶段不能访问节点因为此时还没按中序顺序到达当前节点二是当predecessor.right cur时说明左子树已经全部走完这时候才真正轮到访问cur。代码里把“访问逻辑”放在两个分支的对应位置就是为了保证中序顺序不被破坏。注意Morris遍历会在遍历过程中临时修改树结构但结束时会把所有修改过的right指针恢复。如果遍历完没有恢复后续再操作这棵树就会出现奇怪的问题。面试时可以在结束位置把线索指针置空确保树结构和进来时一致。5. 常见问题与排查技巧实录5.1 97题滚动数组更新方向错乱刷题群里经常看到有人问为什么一维DP的遍历顺序有时候正序、有时候倒序交错字符串这道题就是“依赖左边同行的新值”的典型内层必须正序。如果写成了倒序会出现什么现象dp[j-1]还停留在上一行的值代表的状态是“s1前i-1个字符和s2前j-1个字符”而不是当前想要的“s1前i个字符和s2前j-1个字符”。结果就是漏掉一部分合法匹配输出false。排查技巧很直接把二维表格画出来标出dp[i][j]的两个来源方向一个是正上方一个是正左方。用一维数组从j1到n更新时dp[j]在被覆盖前正好是正上方的值dp[j-1]则已经被当前行更新。两种依赖一次满足。这个“画表看方向”的方法几乎适用于所有双序列DP空间优化题。5.2 98题优化边界值却漏掉相等值有些解法为了只用int会使用Integer.MIN_VALUE和Integer.MAX_VALUE做初始边界。这个思路在普通数据下也能通过测试但遇到节点值等于int极值时会误判。我建议直接用long或者包装类型代码只是多打几个字母却省掉一类隐藏bug。另一个出现频率很高的错误是判断条件写成root.val prev而不是。BST要求左小右大中序序列严格递增所以相等值一定不合法。题目如果约定所有节点值唯一这个问题不会暴露但工程上还是要按严格递增写。5.3 99题second更新和Morris死循环99题最典型的错误是second只在firstnull时赋值。我第一次写的时候就是这样跑简单用例能过一旦遇到两处逆序就出错。排查方法打印中序遍历序列确认被交换的节点位置。如果second停留在第一次逆序的节点说明赋值位置放错了。Morris遍历最常见的问题是死循环。原因往往是“建立线索后没有继续往左走”或者“predecessor.right cur时没有断开线索”。记住一个口诀有左孩子就找前驱前驱右指针为空就挂线索并走左前驱右指针指向自己就断开线索、访问当前节点、走右。三条缺一不可。5.4 三道题的复杂度对照题目解法时间复杂度空间复杂度交错字符串二维DPO(mn)O(mn)交错字符串一维滚动数组O(mn)O(n)验证BST递归上下界O(n)O(H)验证BST迭代中序O(n)O(H)恢复BST递归/栈中序O(n)O(H)恢复BSTMorris中序O(n)O(1)空间复杂度里的H是树高平衡树是O(logn)退化链表是O(n)。如果遇到对空间要求严格的题目Morris遍历几乎是唯一能稳定做到O(1)的选择值得单独练熟。6. 从这三题延伸出去的刷题路线6.1 值得继续练的同类题目97题练完可以顺势把双序列DP这一组刷透。个人推荐的配套题单有LeetCode 10正则表达式匹配、72编辑距离、1143最长公共子序列。这四道题的共同点是都定义dp[i][j]为两个序列前缀的匹配结果转移时都考虑“最后一个字符是否来自第一个序列或第二个序列”。一旦在一道题上把状态定义想清楚其他题会很快。98题和99题练完建议回到二叉树遍历本身。LeetCode 94题二叉树的中序遍历可以用递归、迭代、Morris三种方式分别实现作为手感练习230题二叉搜索树中第K小的元素直接利用中序递增性质501题二叉搜索树中的众数也是中序遍历的变种。刷这些题的时候可以刻意提醒自己“当前中序序列是不是有序的如果不有序意味着什么”这就在训练一种可迁移的直觉。6.2 刷题复盘的个人习惯我不太赞成只追求AC数量。刷完一道题真正有价值的是复盘三个问题第一第一反应为什么错第二正确解法的核心判断是什么第三有没有更省空间的实现以97题为例第一反应是双指针错在贪婪选择无法回溯核心判断是“最后一位来自哪个序列”更省空间的做法是一维滚动数组。这道题就在脑子里形成了一个完整的故事。对99题第一反应一定是中序遍历找逆序对但大多数人不会第一时间想到Morris。我会把“如何省递归/栈空间”单独记成一个小专题等刷到94题时再复习一遍。如果第二天能不看答案把Morris遍历写出来才算真正掌握。最后再分享一个小技巧每天刷题后把三道题的关键状态表示、转移方程或遍历模板写在一张卡片上拍照存进手机的备忘。周末抽出半小时翻一遍比临时抱佛脚刷10道新题有用得多。像97-99这组题把“双序列DP状态定义”和“BST中序找逆序对”提炼成两句话之后遇到类似题目会顺手很多。