企业官网建设流程全解析

2月23日，我按计划把刷题打卡进度推进到LeetCode第97-99题。一天三道题，听起来不算多，但这一组的含金量非常在线：第97题交错字符串是经典的双序列动态规划，第98题验证二叉搜索树和第99题恢复二叉搜索树则是围绕BST中序遍历展开的一组递进式问题。如果你正在准备算法面试、转码复习，或者只是想在一些核心知识点上保持手感，这一组题值得认真过一遍。

三道题分别是两个方向：一个字符串DP，两个二叉树。表面上没什么关联，但它们恰好都适合在“基础模板”之上做优化——97题可以讲清楚滚动数组怎么省空间，98题能把BST的“范围约束”讲透，99题则是中序遍历的进阶应用，甚至能延伸到Morris遍历。一次刷完，等于把DP和树遍历两条主线都练到了。

1. 今日题单概览与刷题思路

1.1 97-99题分别考什么

先把三题的基本信息摆出来，方便对照：

三题的难度阶梯也比较明显：97题是常规的DP思路，状态定义清楚了就完成一大半；98题属于“看似简单但很容易写错”的二叉树题，重点考细节；99题是其中最难的一道，很多人第一次做会卡在“怎么在O(1)空间下完成中序遍历”上。放在同一天刷，刚好可以体会到同一类遍历技巧在不同难度下的应用。

1.2 我为什么把这三题放在同一组

刷题最忌讳零散，今天一道链表、明天一道图论、后天一道贪心，知识点之间没有关联，记不牢。我选择把97-99放在同一天，原因很简单：它们能形成一条逻辑链条。

第97题强调“状态定义”。双序列DP题的通用套路是定义dp[i][j]，然后思考最后一个字符来自哪个序列。这个模板掌握之后，后面遇到编辑距离、最长公共子序列、正则表达式匹配都会轻松很多。

第98题和第99题则是一对“兄弟题”。前者要求判断一棵树是不是BST，后者要求修复一棵不合法BST。两题共用中序遍历这个底层工具。中序遍历在BST中一定会输出递增序列，所以98题靠这个性质检查，99题靠这个性质找错。

这样安排还有一个好处：第二天复盘时不需要重新回忆上下文，只要记住“97是一道字符串DP，98和99是BST中序遍历的两次应用”，整个题组的知识点就都能串起来。对正在准备面试的人来说，这种成组记忆的效率比孤立的题目高很多。

2. 97题：交错字符串的动态规划解法

2.1 先踩一遍双指针的坑

先读题：给三个字符串s1、s2、s3，判断s3能否由s1和s2交错组成。所谓交错，就是s1和s2内部的字符相对顺序都不能变，但两个序列可以互相穿插。

我第一反应是双指针：p1指向s1，p2指向s2，遍历s3，看当前字符匹配哪个指针就移动哪个。这个思路在“当前字符只可能匹配其中一个指针”的时候是有效的，但问题在于，当s3当前字符同时匹配s1和s2时，你无法确定该走哪边。

举个例子：s1 = "ab"，s2 = "aa"，s3 = "aaba"。如果双指针选择先匹配s2，走到某个位置就会卡住，最终误判为false。但实际上s3可以由s1和s2交错组成：s3[0]来自s1的a，s3[1]来自s2的a，s3[2]来自s1的b，s3[3]来自s2的a，完全合法。

这个例子说明，双指针本质是“贪心”，一旦遇到多个可选项，它没有能力判断哪条路是对的。交错字符串需要的是“把每条路都试一遍“的能力，这正是动态规划或者回溯加记忆化能提供的。

2.2 状态定义和转移方程

双序列DP的套路，是先想清楚两个序列各自“走到了哪里”。这里用dp[i][j]表示，s1的前i个字符和s2的前j个字符，能不能交错组成s3的前i+j个字符。

初始状态是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，左孩子3，3的右孩子是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]的两个来源方向，一个是正上方，一个是正左方。用一维数组从j=1到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只在first==null时赋值。我第一次写的时候就是这样，跑简单用例能过，一旦遇到两处逆序就出错。排查方法：打印中序遍历序列，确认被交换的节点位置。如果second停留在第一次逆序的节点，说明赋值位置放错了。

Morris遍历最常见的问题是死循环。原因往往是“建立线索后没有继续往左走”，或者“predecessor.right == cur时没有断开线索”。记住一个口诀：有左孩子就找前驱，前驱右指针为空就挂线索并走左；前驱右指针指向自己就断开线索、访问当前节点、走右。三条缺一不可。

5.4 三道题的复杂度对照

空间复杂度里的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中序找逆序对”提炼成两句话，之后遇到类似题目会顺手很多。