企业官网建设流程全解析

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 = "aabcc"，s2 = "dbbca"，s3 = "aadbbcbcac"，结果是true；如果s3变成"aadbbbaccc"，就是false。

我第一次看到这题，第一反应是双指针：同时遍历s1和s2，遇到s3当前字符，匹配哪个就走哪个。但这个思路很快就会被反例打脸，因为当s3的当前字符同时能匹配s1和s2的当前字符时，你选哪条路直接决定后续是否可行，而双指针做不了“回溯”。这说明什么呢？说明这类“多选一”的路径决策问题，天然适合用动态规划，因为DP本质上就是在枚举所有可能的决策组合，而不是一条路走到黑。

2.2 DP状态定义与转移方程推导

定义dp[i][j]表示s1的前i个字符和s2的前j个字符，能否交错组成s3的前i+j个字符。这个定义的关键在于：不用关心s3剩下的部分怎么组成，只关心当前这两个前缀能不能“拼出”s3对应长度的前缀，把大问题切成小问题。

状态转移分两种情况。第一种情况，s3的第i+j个字符（也就是当前拼出来的最后一个字符）来自s1，那么前提是s1[i-1]等于s3[i+j-1]，并且dp[i-1][j]为true；第二种情况，最后字符来自s2，那么前提是s2[j-1]等于s3[i+j-1]，并且dp[i][j-1]为true。两种情况只要有一种成立，dp[i][j]就是true。

用伪代码表示就是：

dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])

初始条件也要想清楚。dp[0][0]表示两个空串能拼出空串，为true。dp[i][0]只依赖s1连续匹配s3，dp[0][j]只依赖s2连续匹配s3。这些都是“退化情况”，很多bug就出在这里，后面我会专门讲。

2.3 一维滚动数组优化与代码实现

二维dp数组是(m+1)乘(n+1)，空间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[i+j-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题，如果不做滚动数组优化，在m和n都接近1000时，dp数组会占约1MB内存，虽然不算夸张，但面试时主动做优化绝对是加分项。

5.2 刷题时的通用判断套路

刷完这三题，我总结了一套“拿到题先判断类型”的思路。看到“判断是否可行”“有多少种方案”这类问题，优先往DP方向想；看到二叉树且涉及有序性，优先往中序遍历方向想；看到一个题是另一个题的“升级版”，先想能不能复用基础题的结论。比如99题用到的中序有序性，正是98题的核心性质，这说明很多难题只是基础题换了一层外壳。

我还发现一个值得养成的习惯：每道题先想清楚“暴力解法”是什么，再优化。97题的暴力是枚举所有交错路径，98题的暴力是每个节点递归验证子树最大值最小值，99题的暴力是拷贝中序序列到数组再排序比对。暴力解法能帮你看清问题的本质，后面的优化只是减少重复计算或节省空间而已。

6. 常见问题与排查技巧实录

6.1 交错字符串DP的初始化陷阱

97题最经典的报错场景是s3长度不等于s1加s2之和。这个判断一定要放在最前面，否则后面i+j会越界。还有一个隐藏的坑：滚动数组里，dp[j]在i=0这一轮依赖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日这组题，帮我很好地巩固了这个认知。