递归与分治

递归是「我懂这个思路」和「我能在压力下写对」分岔最快的地方。思路一句话就能说清——一个函数靠对更小的实例调用自己来解决大问题——但面试翻车的点非常具体:base case 忘了 return、某个更新神秘地在跨调用后不生效、两个方法互相循环调用把栈撑爆。这一课先把心智模型建立一次,然后把它花在两个战场上:数组和网格上的分治(merge sort、quick select、N-Queens、spiral matrix),以及树上的递归——在树上,递归不是你「选用」的技巧,而是这个数据结构唯一会的遍历方式。

一个递归解法的形状

在任何具体题目之前,这一课先钉死每个递归共有的解剖结构。两种失败模式框住了整个话题。没有缩减参数的直接自调会撑爆栈——经典的无限递归。间接递归更阴:A() 调 B()、B() 调 C()、C() 调 A()——一个同样会溢出、但在 review 里难得多才看得出的环。每个递归都需要一个可证明朝 base case 收敛的缩减。

缩减有两种形状,而且干净地对应到复杂度:

• 线性缩减——f(n) 依赖 f(n-1) 或 f(n-2)。每层剥一个,递归深 O(n)。Fibonacci、climbing stairs(LC 70)、jump game(LC 55)是标准形状——每个状态往回够一到两步。(当这些重叠调用爆炸时,记忆化就把它们变成 DP——那正是通往后两课的桥。)
• 分治——f(n) 依赖 f(n/2)。每层砍一半,递归树只有 O(log n) 深。二分查找是最纯的例子:它丢掉一半空间,只对一边递归。

另外两条规则才是大家真正写错的地方。Base case 必须 return。 一个算对了却忘了返回的 base case 会悄悄穿透下去,把答案污染掉——把 base case 放在一个私有 helper 的顶部。Corner case 归 public method。 null 输入、空数组、单节点——在 public 包装层里一次性检查掉,再把干净、保持不变式的输入交给 helper。这个拆分让递归核心保持小而诚实。

数组上的分治:排序、查找与递归树

数组经典题才是分治名副其实的地方。Merge sort 把数组切成两半,递归排好每一半,再在线性时间内合并两个有序半。Quick sort 绕一个 pivot 做 partition,再对两侧递归。它们的递归树长得一模一样——log n 层、每层 O(n) 的活——这正是这一课倚重的主定理直觉,而不是套公式:画出树,把每层的活加起来,乘以层数。

这个求和值得亲手做至少一次,因为它把复杂度是从哪来的讲透了:

merge / quick sort:   n  +  2·(n/2)  +  4·(n/4)  + ...   = 每层 n × log n 层  =  O(n log n)

求树高 getDepth:     1  +  2  +  4  + ... + 2^(logn-1)  = 2^logn             =  O(n)

N-Queens validate():  n  +  n^2 +  n^3 + ... + n^(n-1)   = O(n^(n+1))   // 注意:不是 O(n^n)

Quick select 是 quick sort 更精简的表亲,也是面试官偏爱的那个:要找第 k 小的元素,partition 一次,然后只往包含 k 的那一侧递归。丢掉另一半,把期望代价从 O(n log n) 压到 O(n)——和二分查找同样的「丢掉一半」直觉,用在了选择上。而二分查找本身,从这个视角看,不过是每次只对一个孩子递归、每层做 O(1) 活的分治。这一课把二分查找描述成「DFS 的扁平版」,这正是本课和下面树部分之间的连接组织。

二维棋盘上的回溯:N-Queens 与 Sudoku

从 1D 迈到 2D,递归就变成回溯(backtracking):试一个选择、递归、在回来的路上撤销这个选择,让下一个分支从干净状态开始。LC 51 N-Queens 是原型——每列(或每行)放一个皇后,每一步只保留跟已放下的不冲突的落法。精妙在冲突检测。因为你从左往右填,新皇后只可能和已放的列冲突,而且只沿三条线:同行、↘ 对角线、↗ 对角线。

对角线恒等式是最该背的技巧:↘ 对角线上 row + col 恒定;↗ 对角线上 row - col 恒定。 这把一次 O(n) 的扫棋盘变成三次 O(1) 的 set 查表。LC 52 N-Queens II 只数解的个数,所以你连棋盘都不用实体化——三个 HashSet 就装下了全部所需状态:

class Solution {
    public int totalNQueens(int n) {
        Set<Integer> cols = new HashSet<>();   // 已占用的 column
        Set<Integer> diag = new HashSet<>();   // row - col  (↘, 135°)
        Set<Integer> anti = new HashSet<>();   // row + col  (↗, 45°)
        return dfs(cols, diag, anti, n, 0, 0);
    }

    private int dfs(Set<Integer> cols, Set<Integer> diag,
                    Set<Integer> anti, int n, int row, int count) {
        for (int col = 0; col < n; col++) {
            if (cols.contains(col))       continue;
            if (diag.contains(row - col)) continue;   // 同一条 ↘ 对角线
            if (anti.contains(row + col)) continue;   // 同一条 ↗ 对角线

            if (row == n - 1) {
                count++;                              // 最后一行填好 → 一个完整解
            } else {
                cols.add(col); diag.add(row - col); anti.add(row + col);
                count = dfs(cols, diag, anti, n, row + 1, count);
                cols.remove(col); diag.remove(row - col); anti.remove(row + col);
            }
        }
        return count;
    }
}

注意诚实的复杂度:如果 validate 是 O(1),N-Queens 是 O(n^(n+1)),而这一课点名了那个容易看错的地方——n^(n+1) 不等于 n^n。用 set 不改变指数级的本质,只是缩小常数、把分支检测写干净。

LC 36 Valid Sudoku 贡献了第二个可复用套路:用一个下标遍历 3×3 的方块。值得背进肌肉记忆的是 squareRow = 3 * (i / 3)、squareCol = 3 * (i % 3) 定位一个方块的左上角,再用 board[squareRow + j/3][squareCol + j%3] 走遍它的九格——% 横向步进,/ 换行下移。LC 37 Sudoku Solver 再把这个合法性检查包进和 N-Queens 一样的回溯循环里:对当前空格,试 '1' 到 '9',合法就放一个、递归,失败就擦掉再试下一个。放 → 递归 → 撤销,就是回溯的心跳。

Spiral Matrix:递归地剥层

LC 54 Spiral Matrix 和 LC 59 Spiral Matrix II 按顺时针螺旋读矩阵,而最干净的表述是递归的:打印最外圈,然后对里面的子矩阵递归。 每次调用处理四条边——顶行从左到右、右列从上到下、底行从右到左、左列从下到上——然后用缩小 2 的维度、加 1 的 offset 再调用自己。绊住新手的两个 base case 是退化的圈:只剩单行(m == 1)或单列(n == 1),必须打印而不重复计角。

这一课里几点能把「排练过的答案」和「心里没底的答案」区分开:它处理非正方矩阵(独立跟踪 m 和 n,而不是一个边长),它不用额外空间(除输出列表外),而且同样逻辑能平凡地改写成 while 循环(m -= 2; n -= 2; offset++)给偏爱迭代的人。对于生成变体,认出坐标到值的公式 matrix[i][j] = i * n + j 就能让填充循环自然掉出来。更大的启示回到本课开头:螺旋不过是「divide 意味着剥掉边界层」的分治。

为什么说树就是递归本身

这里这一课转向,语气也变了。在数组上你「选」递归;在树上你几乎躲不掉,因为树本来就是递归定义的——一个节点是一个值加上一棵左子树和一棵右子树,而每棵子树本身又是一棵树。Base case 自己就写好了:叶子底下的 null。而几乎每道树题都能套进一个三行模板:

1. 问孩子——递归进 root.left 和 root.right。
2. 在这一层做事——合并两个答案,更新任何在跑的状态。
3. 往上返回一个值——这个节点交给父节点的摘要。

这一课把它叫作 bottom-up 模式:信息从叶子往上流,没有节点需要从上面带下来的上下文。凡是长得像「树上 DP」的东西,这都是天然贴合。反方向——top-down,节点把上下文往下传给孩子——也会出现(validate-BST 往下带 min/max 边界;path-sum 往下带累计和),而认出一道题想要哪个方向,就赢了一半。笔记里有个快速信号:反转一切的练习(反转数组、字符串、list、integer、它的 bits、或一棵树)其实是同一个递归穿了六件戏服——交换两个孩子、递归、完事。

高度、平衡与哨兵技巧

求树高是模板最简单的样子:1 + max(height(left), height(right)),base case 在 null 处是 0,总共 O(n)。有教学价值的题是 LC 110 Balanced Binary Tree,因为显然的解法悄悄是平方级的。如果你把 isBalanced 写成在每个节点都调一次单独的 getDepth,你就在 O(n) 个节点上各付 O(n)——平衡树上 O(n log n),最坏 O(n²)。面试官就等着看你注不注意得到。

修法是一个在几十道树题上都能兑现的套路:让 post-order 的返回值捎带额外信息。 把高度函数重定义成用返回 -1 当哨兵,意思是「我下面某棵子树已经不平衡了」。一旦任一孩子报 -1,或高度差超过 1,就返回 -1,失败一路狂奔到 root——单趟,O(n):

// getDepth 兼任平衡检查:-1 表示「我下面已经不平衡」
private int getDepth(TreeNode root) {
    if (root == null) return 0;
    int left  = getDepth(root.left);
    int right = getDepth(root.right);
    if (left == -1 || right == -1 || Math.abs(left - right) > 1)
        return -1;                       // 短路掉整棵子树
    return 1 + Math.max(left, right);
}

public boolean isBalanced(TreeNode root) {
    return getDepth(root) != -1;
}

同样的「存下答案而不是重算」的思路可以推广。如果一道题要 O(1) 查每棵子树的节点数,你没法按需遍历——就预计算并缓存到节点的 field 上(TreeNode.leftSubtreeCount),在一趟 post-order 里填好。LC 222 Count Complete Tree Nodes 就是同一个计数递归(left + right + 1),而边走边把左子树计数塞进 field,正是你日后支持 O(1) 子树大小查询的做法。树是对象;对象能装缓存。

在递归中携带状态:global 还是 wrapper

这是这一课里最能迁移的一个想法,也是只用返回值递归过的强候选人最容易栽的地方。想象:找出左右子树节点数差最大的那个节点。 计数是 bottom-up(又是树高模板),但答案——哪个节点赢了——得活过整趟遍历。保住它有两种办法。

办法一:放在递归外面的变量。 一个 class field——类上的 static,或 new Solution() 上的实例 field——每个栈帧都读写它。简单,面试单线程代码里完全够用。

办法二:传一个 wrapper 参数。 这里就是这一课反复敲的坑:你不能传一个裸的 int。Java 是 pass-by-value——参数复制的是栈上那个值,所以每个栈帧拿到自己私有的 max;子调用里的更新永远到不了父调用。修法是传一个引用被复制、但内容被共享的东西:一个 int[1],或者当你要记住的是节点时用 TreeNode[1]:

int[] max = new int[1];              // heap 对象 → 每个栈帧共享它
TreeNode[] maxNode = new TreeNode[1];

private int countNodes(TreeNode root, int[] max, TreeNode[] maxNode) {
    if (root == null) return 0;
    int left  = countNodes(root.left,  max, maxNode);
    int right = countNodes(root.right, max, maxNode);
    int diff = Math.abs(left - right);
    if (diff > max[0]) {              // 裸的 `int max` 参数不会持久
        max[0] = diff;
        maxNode[0] = root;
    }
    return left + right + 1;          // post-order:先数完孩子再到父
}

这一课自己的说法值得记住:你要的东西,用比它高一级的东西把它包起来。 想改一个 int?包进 int[]。想改「指向哪个 TreeNode」?TreeNode 本来就是对象,但重新赋值本地变量不会传播出去——所以包进 TreeNode[]。这个数组是共享信箱;每个栈帧往同一个信箱里投信。

Lowest Common Ancestor 的四种写法

LC 236 Lowest Common Ancestor of a Binary Tree 是「在返回值里找答案」最干净的演示。递归问每棵子树里有没有 p 或 q。Base case:节点若本身是 p、q 或 null,就返回它自己。合并步骤纯粹是逻辑:只有一边非 null,答案就在那边;若两边都非 null,当前节点就是 p 和 q 分岔的地方——LCA。

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)  return right;   // 两个目标都在右边
    if (right == null) return left;    // 两个目标都在左边
    return root;                        // p 和 q 在此分岔 → LCA
}

这一课接着把同一道题旋出四种写法,每种都是小变体:

• 带 parent 指针——从 p 往上走并标记访问过的节点,再从 q 往上走直到碰到一个被标记的。不需要完整遍历。
• LC 235,BST 上的 LCA——有序性替你干活。LCA 的值一定落在 p.val 和 q.val 之间,于是从 root 往下走:两个目标都更大就往右,都更小就往左,第一个落在两者之间的节点就是答案。轻松写成迭代,O(h)。
• N 个节点而非两个——结构一模一样,只是 base case 更长(节点是任一目标就返回非 null),外加同样的「返回非 null 的那一侧,否则返回它们汇合的节点」。
• K 叉树——不是左/右,而是数有几个孩子返回了非 null:零个 → 返回 null,一个 → 把那个往上冒,多于一个 → 这个节点就是 LCA。

路径和与最大路径

路径这一族是「往下带」和「往上冒」两个方向在同一组题里相遇的地方。LC 112 Path Sum(有没有一条 root-to-leaf 路径命中目标?)和 LC 113 Path Sum II(把它们全返回)把递减的剩余和往下带,而 LC 113 还加了经典回溯列表——进来时 cur.add(root.val),出去时 cur.remove(cur.size()-1)。LC 437 Path Sum III 抬高了门槛:只要往下走,路径可以起止于任意节点。暴力把每个节点固定为起点往下找——最坏 O(n²)、平衡 O(n log n)——但优雅解是 prefix-sum HashMap,two-sum 在树上的表亲:把每个运行前缀和映射到出现过几次,在每个节点查 prefixSum - target。单趟 O(n),配上进入时加、退出时减的回溯,保持 map 是当前路径局部的。

压轴是 LC 124 Binary Tree Maximum Path Sum,这一课的建议一点没错:整个看太难,那就简化。 枚举路径形状——leaf-to-root、node-to-root、leaf-to-leaf——然后往上搭。两个洞察让解法结晶。第一,贡献为负的子树干脆丢掉,所以用 Math.max(0, child) 把每个孩子的贡献夹住。第二,分清节点算的两样东西:在此节点拐弯的最优路径(left + right + val,用来更新全局最大值),和它能往上交的最优路径(max(left, right) + val,因为父节点只能穿过一个孩子来延伸):

class Solution {
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int left  = Math.max(0, dfs(root.left));    // 丢掉负分支
        int right = Math.max(0, dfs(root.right));
        max = Math.max(max, left + right + root.val);   // 在 root 拐弯的路径
        return Math.max(left, right) + root.val;        // 继续往上延伸的路径
    }
}

反方向的信息流出现在 LC 98 Validate BST:正确性不是局部检查(只拿节点跟它直接孩子比,会漏掉来自远方祖先的违规),所以你把 (min, max) 边界往下带,每步收紧——往左走当前值成为新上界,往右走成为新下界。用 long 边界以扛住 Integer.MIN_VALUE/MAX_VALUE 的节点值。同一棵树,相反的流:LC 124 把和往上冒,LC 98 把约束往下推。

重建树:序列化与从遍历构造

收尾把分治重新框成重建:不是拆一个问题,而是拆输入并重建结构。LC 297 Serialize and Deserialize Binary Tree 问一棵树在内存里怎么活、在网线上怎么传。干净的编码是一趟 preorder,对每个 null 写一个哨兵("X");反序列化用一个 queue 读这个流,而因为 preorder 先吐 root,buildTree 弹出一个值,再递归建左、建右——递归和序列化完全镜像。(这一课也点了理论:单个遍历加 null 足以无歧义,任意 inorder + preorder 或 inorder + postorder 组合也一样。)

那个组合就是 LC 105 Construct Binary Tree from Preorder and Inorder。preorder[0] 永远是 root;在 inorder 里找到它,它左边的全是左子树,右边的全是右子树。用调整过的下标窗口对两半递归:

public TreeNode buildTree(int[] preorder, int[] inorder) {
    return helper(0, 0, inorder.length - 1, preorder, inorder);
}

private TreeNode helper(int preStart, int inStart, int inEnd,
                        int[] preorder, int[] inorder) {
    if (preStart > preorder.length - 1 || inStart > inEnd) return null;

    TreeNode root = new TreeNode(preorder[preStart]);   // preorder 头就是 root
    int inIndex = inStart;
    for (int i = inStart; i <= inEnd; i++)
        if (inorder[i] == root.val) inIndex = i;        // inorder 里的切分点

    root.left  = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
    root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
    return root;
}

为找切分点做的线性扫描让它是 O(n log n);一个 值→下标 的 HashMap 把它降到 O(n)。LC 106 是镜像——postorder[last] 是 root,而且你先建右再建左。Level-order + inorder 也是同一配方:level[0] 是 root,绕它切开 inorder,再把 level 序列过滤进两侧。

还有两道重建给这一课收口,都是「挑中间当 root」。LC 108 Convert Sorted Array to BST 取 mid 当 root、对两半递归——白送一棵高度平衡的 BST(笔记点了个细微处:平衡 BST 不唯一,但完全 BST——最后一层靠左——是唯一的)。LC 109 Convert Sorted List to BST 是同一想法搬到链表上,你没法按下标取——所以用 fast/slow 指针在每层 O(n) 找到中间节点。其他改造树的表亲也住在这:LC 114 Flatten Binary Tree to Linked List(一趟反向 preorder,把每个节点的 right 指针串起来、left 置空)和原地的 LC 426 tree-to-doubly-linked-list,它利用 TreeNode 本来就有两个指针这一点——把 left/right 复用成 prev/next,在一趟 inorder 里串好,不用额外空间。

刷题清单