递归数据结构
啥叫递归数据结构？你看链表，一个节点后面跟着另一个节点，这不就是自己套自己嘛。你看二叉树，一个根节点下面连着左子树、右子树，子树本身又是二叉树。对付这种结构，递归就是最顺手的兵器。
16.2.1 从链表中移除结点
问题描述：
给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
示例： 输入: head = [1,2,6,3,4,5,6], val = 6 输出: [1,2,3,4,5]
思路分析：
这题太经典了，面试手撕代码经常遇到。
解法一：迭代 + 哨兵节点（Dummy Head）
拿到链表题，尤其是涉及到可能删除头节点的操作，我第一反应就是搞一个虚拟头节点（Dummy Head）。为啥？因为它可以让所有节点的删除操作都统一起来，不用单独处理头节点被删除的特殊情况，代码写起来极其舒爽。
思路很简单：
创建一个
dummy节点，让dummy.next= head。创建一个
cur指针，初始指向dummy。如果
cur.next.val是我们要删除的值，那就直接cur.next=cur.next.next，相当于把cur.next这个节点从链表里“摘出去”了。如果不是，那
cur就正常后移，cur =cur.next。最后返回
dummy.next，这就是新的头节点。
// 链表节点定义
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
// 解法一：迭代 + 虚拟头节点
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}
解法二：迭代，不使用虚拟头节点
有人就头铁，说我不想用额外空间，不用虚拟节点行不行？也行，就是代码得多写几行，处理头节点这个特殊情况。
思路：
先把头节点搞定。如果
head本身就是val，那就一直往后挪，head =head.next，直到找到一个不等于val的新头或者head变成null。处理完头节点，剩下的就跟解法一的逻辑类似了。用一个
cur指针从head开始遍历，判断cur.next，然后决定要不要删除。
// 解法二：迭代，不使用虚拟头节点
public ListNode removeElements_NoDummy(ListNode head, int val) {
// 1. 处理头节点可能被删除的情况
while (head != null && head.val == val) {
head = head.next;
}
if (head == null) {
return null;
}
// 2. 处理非头节点
ListNode cur = head;
while (cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
你看，是不是麻烦一点？所以面试时，除非面试官明确要求，不然直接上虚拟头节点，稳！
解法三：递归大法
这才是本章的重点。怎么用递归想这个问题？咱们可以这么定义一个函数 remove(node, val)：它的功能是，删除以 node 为头节点的链表中所有值为 val 的节点，并返回处理后新链表的头节点。
好，定义清楚了，接下来就是递归的套路：
Base Case（递归出口）：如果
node是null，那没啥可删的，直接返回null。递归过程：
我不管后面的链表有多长，我先让我的小弟（递归调用）去把
node.next后面的部分处理好。也就是调用remove(node.next, val)。这会返回一个已经删除了所有val的新子链表的头。我把这个返回的新子链表头接在
node.next上：node.next= remove(node.next, val)。现在，
node的后面已经完美了。我只需要关心node自己是不是该被删除。如果
node.val == val，那node自己也得滚蛋，应该返回它的下一级，也就是node.next（这个node.next已经是处理好的子链表头了）。如果
node.val != val，那node留下，它就是处理后链表的头，返回node。
这思路是不是特别清晰？我只管好我自己这一层，剩下的事儿甩锅给下一层。
// 解法三：递归
public ListNode removeElements_Recursive(ListNode head, int val) {
// Base Case
if (head == null) {
return null;
}
// 把“除了我之外”的链表先处理好
head.next = removeElements_Recursive(head.next, val);
// 然后再看我自己该不该被删
if (head.val == val) {
return head.next; // 我被删了，返回我的下一个节点作为新的头
} else {
return head; // 我不用删，我还得是头
}
}
你看这代码，多简洁，完美体现了递归的魅力。
16.2.2 合并两个有序链表
问题描述：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的节点组成的。
示例： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
思路分析：
又是一道经典到不能再经典的题。
解法一：迭代 + 哨兵节点
这个思路和上一题解法一很像，也是用一个虚拟头节点来简化操作。
创建一个
dummy节点作为新链表的头，再来一个tail指针，用于在新链表上追加节点。比较
l1和l2当前节点的值。谁小，就把谁接到
tail后面，然后tail和那个被接上的链表的指针同时后移。循环直到
l1或l2有一个变成null。最后，把没遍历完的那个链表剩下的部分，直接接到
tail的后面。返回
dummy.next。
// 解法一：迭代
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
// 处理剩下的链表
tail.next = l1 == null ? l2 : l1;
return dummy.next;
}
这方法非常稳健，时间复杂度 O(m+n)，空间复杂度 O(1)。
解法二：递归
递归解法同样优雅。我们定义函数 merge(l1, l2) 的作用是合并 l1 和 l2，并返回合并后新链表的头。
Base Case：如果
l1是null，那没啥好合的，直接返回l2。同理，l2是null就返回l1。递归过程：
这个过程就像是在剥洋葱，我只决定当前最小的节点是谁，然后把剩下的合并任务交给下一层递归。
// 解法二：递归
public ListNode mergeTwoLists_Recursive(ListNode l1, ListNode l2) {
// Base Case
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
// 递归过程
if (l1.val <= l2.val) {
l1.next = mergeTwoLists_Recursive(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists_Recursive(l1, l2.next);
return l2;
}
}
递归解法的缺点是会消耗栈空间，如果链表特别长，可能会有栈溢出的风险。但代码是真的漂亮。
解法三：原地修改（其实就是迭代的另一种视角）
这个解法本质上还是迭代，但我们可以换个角度思考，不创建新节点（虽然解法一也没创建，只是用了指针），而是将一个链表的节点“插入”到另一个链表中。我们可以假设 l1 是主链表，把 l2 的节点一个个塞进去。
这个思路相对复杂一点，要处理的指针和边界情况更多，容易出错，面试时不推荐。它和解法一本质上都是 O(1) 空间复杂度的迭代，没有性能优势，徒增了实现的复杂性。所以，咱们还是老老实实用带虚拟头节点的迭代或者递归，这两种是正道。为了凑数，我就不写这个容易出错的代码了，掌握前两种足够横着走了。
16.2.3 二叉树剪枝
问题描述:
给定二叉树根结点
root，此外树的每个结点的值要么是 0 要么是 1。 返回移除了所有不包含 1 的子树的原二叉树。 (节点 X 的子树为 X 本身，以及所有 X 的后代。)
示例: 输入: [1,null,0,0,1] 输出: [1,null,0,null,1] 解释: 只有红色节点满足条件“所有节点的值都是 1”。 右图表示我们保留的结果。
思路分析:
这题是后序遍历的绝佳应用场景。为啥？因为我要判断一个父节点该不该被剪掉，得先知道它的左右子树是不是“全0”子树，是不是应该被剪掉。这不就是典型的“先处理孩子，再处理老子”的后序遍历思想嘛。
解法一：递归（后序遍历思想）
定义一个函数 pruneTree(node)，它的作用是：修剪以 node 为根的树，并返回修剪后新树的根。
Base Case: 如果
node是null，直接返回null。递归过程:
先去修剪左子树：
node.left = pruneTree(node.left)。再去修剪右子树：
node.right = pruneTree(node.right)。现在，
node的左右子树都已经是修剪过的“干净”版本了。我们该决定node自己是否要被剪掉。node被剪掉的条件是什么？它自己是 0，并且它修剪后的左子树是null，修剪后的右子树也是null。如果满足这个条件，那么以
node为根的这整个子树都是“全0”子树，应该被剪掉，所以返回null。否则，
node就应该被保留，返回node。
这个后序遍历的思路，完美地解决了问题。
// 树节点定义
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// 解法一：递归
public TreeNode pruneTree(TreeNode root) {
if (root == null) {
return null;
}
// 后序遍历位置：先处理子树
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
// 处理当前节点：判断自己是否该被剪掉
if (root.val == 0 && root.left == null && root.right == null) {
return null; // 剪掉自己
}
return root; // 保留自己
}
解法二：递归 + 辅助函数判断
上面的解法把“修剪”和“判断是否全0”两个功能合二为一了，非常简洁。我们也可以把它们拆开，思路更清晰。
定义一个辅助函数 containsOne(node)，判断以 node 为根的子树是否包含 1。
containsOne(node)的逻辑：Base Case:
node == null，返回false。递归看左子树是否包含 1：
leftContains = containsOne(node.left)。递归看右子树是否包含 1：
rightContains = containsOne(node.right)。如果左子树不包含 1 (
!leftContains)，就把左子树剪掉：node.left = null。如果右子树不包含 1 (
!rightContains)，就把右子树剪掉：node.right = null。最后，只要
node.val == 1或者leftContains或者rightContains任何一个为真，就说明以node为根的（原始）子树包含 1，返回true。
主函数里，调用 containsOne(root)。如果它返回 false，说明整个树都不含 1，直接返回 null。否则，返回处理过的 root。
// 解法二：递归 + 辅助函数
public TreeNode pruneTree_WithHelper(TreeNode root) {
if (containsOne(root)) {
return root;
} else {
return null;
}
}
private boolean containsOne(TreeNode node) {
if (node == null) {
return false;
}
// 递归地判断左右子树是否包含1
boolean leftContains = containsOne(node.left);
boolean rightContains = containsOne(node.right);
// 根据判断结果进行剪枝
if (!leftContains) {
node.left = null;
}
if (!rightContains) {
node.right = null;
}
// 返回以当前节点为根的（原始）子树是否包含1
return node.val == 1 || leftContains || rightContains;
}
这个解法虽然代码多了点，但职责更分明，也更容易理解。它本质上也是后序遍历，判断发生在递归返回之后。
解法三：其实没有本质区别的第三种解法
所有基于递归的解法，本质都是后序遍历。我们可以变体一下，让递归函数返回布尔值，表示是否要保留当前节点，同时通过引用修改树。但Java中没有引用传递，所以通常还是返回节点本身最方便。前两种解法已经覆盖了最核心、最高效的思路。硬要说第三种，可能就是用迭代+栈模拟后序遍历，但那纯属给自己找麻烦，代码会变得极其复杂，完全失去了二叉树递归解法的简洁之美，面试官看了都得皱眉头。所以，这题掌握好第一种递归解法就足够了。
16.2.4 二叉树的最近公共祖先 (LCA)
问题描述:
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
思路分析:
LCA是二叉树里的一个重头戏，解法多样，但递归解法是最精妙的。
解法一：递归（后序遍历思想）
这个解法的思想非常巧妙。我们定义函数 lowestCommonAncestor(root, p, q) 的含义是：在以 root 为根的树里查找 p 和 q 的LCA。
递归过程是这么设计的：
Base Case：
如果
root是null，说明这条路走到底了也没找到，返回null。如果
root本身就是p或者q，根据定义，它就是LCA（或者LCA的候选之一），直接返回root。
递归分解：
去左子树里找
p和q的LCA：left = lowestCommonAncestor(root.left, p, q)。去右子树里找
p和q的LCA：right = lowestCommonAncestor(root.right, p, q)。
结果合并：这一步是精髓。递归调用返回后，
left和right的值有几种情况：如果
left和right都非空：这意味着什么？p和q分别在root的左右两棵子树里！那root不就是它俩的LCA嘛！直接返回root。如果
left非空，right为空：这说明p和q都在左子树里，并且左子树的递归调用已经帮我们找到了它俩的LCA，就是left。所以我们直接返回left就行。如果
left为空，right非空：同理，p和q都在右子树，LCA就是right。如果
left和right都为空：说明左右子树里都找不到p和q，返回null。
你看，整个过程就像信息在逐层向上传递，非常优雅。
// 解法一：递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Base Case
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 && right != null) {
// p和q在异侧，当前root就是LCA
return root;
}
if (left != null) {
// p和q都在左子树，LCA在左子树
return left;
}
if (right != null) {
// p和q都在右子树，LCA在右子树
return right;
}
return null;
}
解法二：存储父节点 + 哈希表
如果不能用递归，或者想换个思路，可以这样做：
先遍历一遍整个树，用一个哈希表
Map<TreeNode, TreeNode>记录下每个节点的父节点是谁。有了父节点信息，找
p的LCA就变成了找从p到根节点的路径。我们可以先把这条路径上的所有节点（包括p自己）都存到一个HashSet里。然后，再从
q开始，沿着它的父节点往上走，遇到的第一个也存在于HashSet里的节点，就是p和q的LCA。
这就像是找两条相交链表的第一个交点，只不过链表是通过父指针串起来的。
// 解法二：存储父节点
public TreeNode lowestCommonAncestor_ParentMap(TreeNode root, TreeNode p, TreeNode q) {
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
Deque<TreeNode> stack = new ArrayDeque<>();
parentMap.put(root, null);
stack.push(root);
// 1. 遍历树，填充parentMap
while (!parentMap.containsKey(p) || !parentMap.containsKey(q)) {
TreeNode node = stack.pop();
if (node.left != null) {
parentMap.put(node.left, node);
stack.push(node.left);
}
if (node.right != null) {
parentMap.put(node.right, node);
stack.push(node.right);
}
}
// 2. 从p往上走到根，记录路径
Set<TreeNode> ancestors = new HashSet<>();
while (p != null) {
ancestors.add(p);
p = parentMap.get(p);
}
// 3. 从q往上走，遇到的第一个p的祖先就是LCA
while (!ancestors.contains(q)) {
q = parentMap.get(q);
}
return q;
}
这个方法需要额外的空间存父节点和路径，时间上也要遍历两次（一次建表，一次查找），不如递归解法简洁高效。
解法三：其实还是递归，但返回信息更丰富
解法一虽然巧妙，但它有一个前提：p 和 q 必须存在于树中。如果 p 或 q 可能不存在，解法一就会出问题。我们可以设计一个返回信息更丰富的递归。
比如，定义一个类 ResultType(TreeNode node, boolean findP, boolean findQ)，递归函数返回这个类的实例。 node 表示找到的LCA候选，findP 表示是否找到了 p，findQ 表示是否找到了 q。
这个过程就复杂了，需要合并左右子树返回的 ResultType，判断当前root是不是LCA，然后构造一个新的 ResultType 向上返回。这其实是把解法一的隐式逻辑显式化了，代码会啰嗦很多，但更鲁棒。在常规面试中，解法一已经足够惊艳了，除非面试官追问节点可能不存在的情况，否则没必要上这么复杂的结构。
这里就不写代码了，因为思路和解法一是一脉相承的，只是把判断逻辑复杂化了。
16.2.5 二叉树展开为链表
问题描述:
给你二叉树的根结点
root，请你将它展开为一个单链表。
展开后的单链表应该同样使用
TreeNode，其中right指针指向链表中下一个结点，而left指针始终为null。展开后的单链表应该与二叉树 先序遍历 的顺序相同。
示例: 输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
思路分析:
这题要求把一个二叉树原地拍平，变成一个链表。顺序是先序遍历的顺序。
解法一：递归（后序遍历思想）
这题用递归解，思路有点反直觉。虽然要求是先序遍历的顺序，但处理起来用后序遍历的思路最方便。
我们定义一个 flatten(node) 函数，它的作用是把以 node 为根的子树拍平。
Base Case:
node为null，直接返回。递归过程:
先把左子树拍平：
flatten(node.left)。再把右子树拍平：
flatten(node.right)。好了，现在
node的左右子树都已经是拉直的链表了。我们要做的是把它们和node拼接起来。怎么拼？顺序是
根 -> 左子树链表 -> 右子树链表。步骤如下： a. 记录下
node原来的左子树（现在是链表头）left和右子树（现在是链表头）right。 b.node.left = null。 c.node.right = left(把左子树链表接到根节点的右边)。 d. 找到左子树链表的末尾节点。这个末尾节点需要接上右子树链表的头。所以，一路cur = cur.right找到这个末尾。 e.cur.right = right。
这个后序遍历的思路，确保了我们在处理一个节点时，它的左右子树已经被处理好了，我们只需要做拼接工作。
// 解法一：递归（后序遍历）
public void flatten(TreeNode root) {
if (root == null) {
return;
}
// 递归地拉平左右子树
flatten(root.left);
flatten(root.right);
// 后序遍历位置：开始拼接
TreeNode left = root.left; // 拉平后的左子树链表
TreeNode right = root.right; // 拉平后的右子树链表
// 1. 将左子树作为新的右子树
root.left = null;
root.right = left;
// 2. 找到新右子树（原左子树）的末尾
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
// 3. 将原右子树接到末尾
p.right = right;
}
解法二：递归（记录前驱节点）
解法一每次都要遍历左子树链表去找尾巴，有点浪费。咱们可以优化一下。 换个思路，还是后序遍历，但我们维护一个全局或通过引用传递的 prev 节点，表示上一个被访问的节点。 遍历顺序是 右 -> 左 -> 根（反向的先序遍历）。 当我们处理 node 时，prev 刚好是它在先序遍历中的后继节点。
定义一个全局变量
prev = null。递归函数
flatten_rev(node)：Base Case:
node为null，返回。递归处理右子树：
flatten_rev(node.right)。递归处理左子树：
flatten_rev(node.left)。处理当前节点
node：node.right = prev(把当前节点的右指针指向它的后继)。node.left = null。更新
prev = node(当前节点成为下一个节点的前驱)。
这个思路非常巧妙，避免了重复查找尾节点的问题。
// 解法二：递归（反向先序遍历）
private TreeNode prev = null;
public void flatten_rev(TreeNode root) {
if (root == null) {
return;
}
// 倒着来：右 -> 左 -> 根
flatten_rev(root.right);
flatten_rev(root.left);
// 处理当前节点
root.right = prev;
root.left = null;
prev = root; // 更新 prev 为当前节点
}
解法三：迭代（寻找前驱节点）
我们也可以不用递归，用迭代来模拟这个过程。 思路是：对于当前节点 curr，找到它左子树的最右节点（这个节点是 curr 在先序遍历中的前驱）。然后把 curr 的右子树，接到这个前驱节点的右边，再把 curr 的左子树，整体移到 curr 的右边。
让
curr指向root，开始循环，直到curr为null。如果
curr有左子树：找到左子树的最右节点，我们叫它
predecessor。让
predecessor.right = curr.right。让
curr.right = curr.left。让
curr.left = null。
处理完当前
curr后，移动到下一个节点：curr = curr.right。
这其实是 Morris 遍历思想的一个应用。
// 解法三：迭代
public void flatten_iterative(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
// 找到左子树的最右节点（前驱）
TreeNode predecessor = curr.left;
while (predecessor.right != null) {
predecessor = predecessor.right;
}
// 拼接
predecessor.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
// 移动到下一个节点
curr = curr.right;
}
}
16.3 基于归纳的递归算法设计
这一类问题，数据结构本身不一定是递归的，但问题的解法可以被归纳成一个递归的形式。本质上就是“大问题”可以分解成规模更小的“子问题”。
16.3.1 电话号码的字母组合
问题描述:
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例: 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
思路分析:
这题是典型的回溯（Backtracking）问题，而回溯天然就是用递归来实现的。
解法一：回溯（DFS）
回溯算法，说白了就是在一个决策树上做深度优先搜索（DFS）。 我们定义一个 backtrack(index, path) 函数：
index: 当前正在处理digits字符串的第几个字符。path: 从根节点到当前节点已经形成的字母组合（一个StringBuilder）。
递归出口: 如果
index等于digits的长度，说明我们已经处理完了所有数字，得到了一个完整的组合。把path的内容加入结果集res，然后返回。递归过程:
获取当前数字
digits[index]对应的字母们，比如 '2' 对应 "abc"。遍历这些字母（'a', 'b', 'c'）。
做选择: 把当前字母（比如 'a'）追加到
path后面。进入下一层决策: 递归调用
backtrack(index + 1, path)，去处理下一个数字。撤销选择: 当下一层的递归返回后，要把刚才追加的字母从
path中删除，这样才能回去尝试其他的选择（比如 'b'）。这个“撤销”就是回溯的精髓。
// 解法一：回溯
class Solution_LetterCombinations {
private String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> res;
public List<String> letterCombinations(String digits) {
res = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return res;
}
backtrack(digits, 0, new StringBuilder());
return res;
}
private void backtrack(String digits, int index, StringBuilder path) {
// 递归出口
if (index == digits.length()) {
res.add(path.toString());
return;
}
// 获取当前数字对应的字母
String letters = map[digits.charAt(index) - '0'];
for (char c : letters.toCharArray()) {
// 做选择
path.append(c);
// 进入下一层
backtrack(digits, index + 1, path);
// 撤销选择
path.deleteCharAt(path.length() - 1);
}
}
}
解法二：队列（BFS）
除了深度优先的思路，我们也可以用广度优先（BFS）来解决。 这个思路很像按层遍历。
初始化一个队列
queue，里面只放一个空字符串""。遍历
digits里的每个数字。对于每个数字，比如 '2' 对应的 "abc"：
看一下当前队列里有多少个元素（比如
size）。循环
size次，把队列里的老组合一个个取出来。对于每个取出来的老组合
s（比如 "a"），把它和 "abc" 的每个字母拼接，形成新组合（"aa", "ab", "ac"），然后把这些新组合入队。
当所有数字都处理完后，队列里剩下的就是所有最终的组合。
// 解法二：队列（BFS）
public List<String> letterCombinations_BFS(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
Queue<String> queue = new LinkedList<>();
queue.offer("");
for (char digit : digits.toCharArray()) {
String letters = map[digit - '0'];
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
String current = queue.poll();
for (char letter : letters.toCharArray()) {
queue.offer(current + letter);
}
}
}
result.addAll(queue);
return result;
}
这个方法也很巧妙，用队列的先进先出特性，一层一层地生成组合。
解法三：纯递归（不带显式回溯）
这种解法也可以看作递归，但形式上和标准回溯模板略有不同。它通过函数返回值来传递和构建结果。 定义 combine(digits_substring) 返回该子字符串能生成的所有组合。 combine("23") 的结果，可以由 combine("3") 的结果（["d", "e", "f"]）和 '2' 对应的 "abc" 组合而成。 即 'a' + ["d", "e", "f"] -> ["ad", "ae", "af"]， 'b' + ...， 'c' + ... 这个思路自底向上构建，也是一种递归思想。
// 解法三：纯粹的递归分解
public List<String> letterCombinations_PureRecursive(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// Base Case
if (digits.length() == 1) {
String letters = map[digits.charAt(0) - '0'];
for (char c : letters.toCharArray()) {
result.add(String.valueOf(c));
}
return result;
}
// 递归分解
char firstDigit = digits.charAt(0);
String remainingDigits = digits.substring(1);
List<String> subCombinations = letterCombinations_PureRecursive(remainingDigits);
String firstLetters = map[firstDigit - '0'];
for (char c : firstLetters.toCharArray()) {
for (String s : subCombinations) {
result.add(c + s);
}
}
return result;
}
这种方法虽然可行，但在Java里由于字符串拼接会产生很多临时对象，效率可能不如回溯法里的 StringBuilder 高。
后面的几个小题比较简单，咱们快速过一下。
16.3.2 位 1 的个数
问题描述:
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。
思路分析:
解法一：循环与位移动
最直观的，循环32次（因为int是32位），每次检查最后一位是不是1，然后把数右移一位。
// 解法一：循环检查每一位
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if ((n & 1) == 1) {
count++;
}
n >>>= 1; // 无符号右移
}
return count;
}
注意要用无符号右移 >>>，否则对于负数，高位会补1，导致死循环。
解法二：巧妙的位运算 n & (n - 1)
这是一个非常有名的技巧。n & (n - 1) 的作用是：将 n 的二进制表示中最低位的那个 1 置为 0。 比如 n = 6 (二进制 0110)，n-1 = 5 (二进制 0101)。n & (n-1) 就是 0100 (4)。 我们只需要不断重复这个操作，直到 n 变成0，操作了多少次，就有多少个1。
// 解法二：n & (n-1)
public int hammingWeight_trick(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
这是面试中最受欢迎的解法，高效且秀出了你的位运算功底。
解法三：调用库函数
调包侠来了。Java的 Integer 类里直接提供了这个方法。
// 解法三：库函数
public int hammingWeight_lib(int n) {
return Integer.bitCount(n);
}
写业务代码这么写没问题，面试要是这么写，估计就直接下一位了。
16.3.3 2 的幂
问题描述:
给你一个整数 n，请你判断它是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
思路分析:
解法一：循环除法
不断地用n除以2，如果中间某一步余数不是0（除了最后n=1的情况），那就不是。
// 解法一：循环
public boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
while (n % 2 == 0) {
n /= 2;
}
return n == 1;
}
解法二：位运算
2的幂的二进制表示有一个特点：只有一位是1，其他全是0。比如 1(0001), 2(0010), 4(0100), 8(1000)。 那么，利用上题的 n & (n-1) 技巧，如果一个数是2的幂，那么 n & (n-1) 的结果一定是0。 别忘了处理 n <= 0 的情况。
// 解法二：位运算
public boolean isPowerOfTwo_bit(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
一行代码，简洁优雅，面试官最爱。
解法三：数学方法
最大的 int 型 2 的幂是 2^30。如果 n 是 2 的幂，那它必然能整除这个最大的 2^30。
// 解法三：数学
public boolean isPowerOfTwo_math(int n) {
int maxPowerOfTwo = 1 << 30; // 2^30
return n > 0 && (maxPowerOfTwo % n == 0);
}
这算是个取巧的办法，利用了 int 范围的限制。
16.3.4 字符串解码
问题描述:
给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为:
k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
示例: 输入： s = "3[a]2[bc]" 输出： "aaabcbc"
思路分析:
这题用栈来做最合适，括号匹配问题嘛，天然适合用栈。
解法一：双栈（一个存数字，一个存字符串）
遍历字符串：
遇到数字，解析出来，压入数字栈
numStack。遇到
[，把当前正在拼接的字符串res压入字符串栈strStack，然后res清空，准备拼接[内部的内容。遇到字母，直接拼接到当前
res上。遇到
]，这是关键。从numStack弹出一个数字k，从strStack弹出一个字符串prev_res。然后把当前res重复k次，拼接到prev_res后面，形成新的res。
// 解法一：双栈
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int multi = 0;
Deque<Integer> numStack = new LinkedList<>();
Deque<StringBuilder> strStack = new LinkedList<>();
for (char c : s.toCharArray()) {
if (c >= '0' && c <= '9') {
multi = multi * 10 + (c - '0');
} else if (c == '[') {
numStack.push(multi);
strStack.push(res);
multi = 0;
res = new StringBuilder();
} else if (c == ']') {
int k = numStack.pop();
StringBuilder temp = strStack.pop();
for (int i = 0; i < k; i++) {
temp.append(res);
}
res = temp;
} else {
res.append(c);
}
}
return res.toString();
}
解法二：递归
字符串本身就带有递归的结构 k[...]。我们可以定义一个递归函数来解码。 用一个全局索引或者引用来跟踪当前处理到字符串的哪个位置。 递归函数 dfs(s) 的作用是解码 s 的一部分，直到遇到 ] 或者字符串末尾。
// 解法二：递归
class Solution_DecodeString {
int index = 0;
public String decodeString_recursive(String s) {
StringBuilder res = new StringBuilder();
int multi = 0;
while (index < s.length()) {
char c = s.charAt(index);
if (c >= '0' && c <= '9') {
multi = multi * 10 + (c - '0');
index++;
} else if (c == '[') {
index++; // skip '['
String sub = decodeString_recursive(s);
for (int i = 0; i < multi; i++) {
res.append(sub);
}
multi = 0;
} else if (c == ']') {
index++; // skip ']'
return res.toString(); // 一层递归结束
} else {
res.append(c);
index++;
}
}
return res.toString();
}
}
递归解法把状态（比如 multi 和当前的 res）保存在了每一层的函数栈帧里，也很清晰。
解法三：单栈
其实可以只用一个栈，栈里存数字或者已解码的字符串片段。但这样处理起来类型不统一，比较麻烦。双栈的思路是最清晰的。硬要说第三种，可以看作是双栈思路的变种，比如栈里存一个 Pair<Integer, StringBuilder> 对象，把数字和字符串绑在一起入栈，本质没变。所以这题掌握双栈和递归就足够了。
两两交换链表中的节点
问题描述:
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例: 输入: head = [1,2,3,4] 输出: [2,1,4,3]
解法一：迭代 + 虚拟头节点
这题画个图就很清楚了。我们需要三个指针来操作：一个指向要交换的两个节点的前一个节点 prev，一个指向第一个节点 node1，一个指向第二个节点 node2。 prev -> node1 -> node2 -> next_pair_start 交换后变成： prev -> node2 -> node1 -> next_pair_start 然后更新 prev 到 node1，继续下一轮。用虚拟头节点可以简化对头两个节点的处理。
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while (prev.next != null && prev.next.next != null) {
ListNode node1 = prev.next;
ListNode node2 = prev.next.next;
// 交换
prev.next = node2;
node1.next = node2.next;
node2.next = node1;
// 移动prev到下一对的前面
prev = node1;
}
return dummy.next;
}
解法二：递归
递归的定义 swap(node)：两两交换以 node 开头的链表，并返回交换后新链表的头。
Base Case:
node为空或只有一个节点，没得换，直接返回node。递归过程:
我需要交换的两个节点是
node和node.next。交换后的新头是
node.next。我们叫它newHead。那
node应该接在哪里？它应该接在后面那一大串链表交换好之后的新链表头上。后面那一大串是
newHead.next开始的，所以我们递归调用swap(newHead.next)。于是，
node.next= swap(newHead.next)。最后，
newHead应该指向node，所以newHead.next= node。返回
newHead。
public ListNode swapPairs_recursive(ListNode head) {
// Base Case
if (head == null || head.next == null) {
return head;
}
// 待交换的两个节点
ListNode node1 = head;
ListNode node2 = head.next;
// node1 应该连接到 后面交换好的链表的头部
node1.next = swapPairs_recursive(node2.next);
// node2 应该成为新的头部，并指向 node1
node2.next = node1;
// 返回新头部
return node2;
}
解法三：迭代，指针操作的另一种写法
本质还是迭代，只是指针的命名和移动方式上略有不同，但核心思想都是操作三个节点的关系。解法一的写法已经非常经典和清晰了，没必要再搞一个花里胡哨但易错的版本。所以我们还是聚焦前两种，一种代表迭代的缜密，一种代表递归的优雅。
螺旋矩阵
问题描述:
给你一个
m行n列的矩阵matrix，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例: 输入: matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出: [1,2,3,6,9,8,7,4,5]
解法一：按层模拟
这个最直观。我们可以想象成一层一层地“剥洋葱”。 设置四个边界：top, bottom, left, right。 在一个循环里，只要 top <= bottom 并且 left <= right，就执行四步：
从
left到right遍历top行。然后top++。从
top到bottom遍历right列。然后right--。从
right到left遍历bottom行。然后bottom--。从
bottom到top遍历left列。然后left++。 注意在第3、4步之前要加判断，防止单行或单列时重复遍历。
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return res;
}
int rows = matrix.length, cols = matrix[0].length;
int left = 0, right = cols - 1, top = 0, bottom = rows - 1;
while (left <= right && top <= bottom) {
// 从左到右
for (int i = left; i <= right; i++) res.add(matrix[top][i]);
top++;
// 从上到下
for (int i = top; i <= bottom; i++) res.add(matrix[i][right]);
right--;
// 关键判断：防止单行/单列时重复
if (top <= bottom) {
// 从右到左
for (int i = right; i >= left; i--) res.add(matrix[bottom][i]);
bottom--;
}
if (left <= right) {
// 从下到上
for (int i = bottom; i >= top; i--) res.add(matrix[i][left]);
left++;
}
}
return res;
}
解法二：模拟行走 + 标记已访问
我们可以模拟一个人在矩阵里走。定义四个方向 (0, 1), (1, 0), (0, -1), (-1, 0)。 每当要撞墙（越界）或者走到一个已经访问过的格子时，就顺时针转个弯。 用一个和 matrix 等大的 visited 数组来标记。
public List<Integer> spiralOrder_simulation(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix.length == 0) return res;
int rows = matrix.length, cols = matrix[0].length;
boolean[][] visited = new boolean[rows][cols];
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
int dirIndex = 0;
int r = 0, c = 0;
for (int i = 0; i < rows * cols; i++) {
res.add(matrix[r][c]);
visited[r][c] = true;
int nextR = r + directions[dirIndex][0];
int nextC = c + directions[dirIndex][1];
if (nextR < 0 || nextR >= rows || nextC < 0 || nextC >= cols || visited[nextR][nextC]) {
dirIndex = (dirIndex + 1) % 4; // 转向
}
r += directions[dirIndex][0];
c += directions[dirIndex][1];
}
return res;
}
解法三：递归
这可以看作是解法一的递归版本。 定义一个递归函数，负责打印最外一圈，然后对小一圈的内部矩阵进行递归调用。 这个实现起来容易出错，边界条件特别多，不如迭代清晰。但思路是成立的。
后面的题目比较类似，我快速给出核心思路和代码。
移除链表元素
这个问题在 16.2.1 已经详细讲过了，这里不再赘述，请参考前面的三种解法。
回文链表
问题描述:
请判断一个链表是否为回文链表。
解法一：转成数组
最蠢的办法，遍历链表，把值存到 ArrayList 里，然后用双指针判断数组是不是回文。时间O(N)，空间O(N)。
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<>();
ListNode curr = head;
while (curr != null) {
vals.add(curr.val);
curr = curr.next;
}
int left = 0, right = vals.size() - 1;
while (left < right) {
if (!vals.get(left).equals(vals.get(right))) {
return false;
}
left++;
right--;
}
return true;
}
解法二：快慢指针 + 反转后半部分
这是最优解。空间O(1)。
用快慢指针找到链表中点。
反转后半部分链表。
用两个指针，一个从头开始，一个从反转后的后半部分头开始，逐一比较。
（可选）恢复链表结构。
public boolean isPalindrome_optimal(ListNode head) {
if (head == null) return true;
// 1. 找中点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 反转后半部分
ListNode secondHalf = reverse(slow.next);
// 3. 比较
ListNode p1 = head;
ListNode p2 = secondHalf;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 4. 恢复链表（可选）
slow.next = reverse(secondHalf);
return result;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
解法三：递归
递归的思路是，利用递归的调用栈，实现“从后往前”的比较。 定义一个全局的 left 指针指向头部。递归函数深入到链表末尾，然后随着栈帧的回退，用全局的 left 指针和当前递归的 right 节点进行比较。
private ListNode frontPointer;
public boolean isPalindrome_recursive(ListNode head) {
frontPointer = head;
return recursivelyCheck(head);
}
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) {
return false;
}
if (currentNode.val != frontPointer.val) {
return false;
}
frontPointer = frontPointer.next;
}
return true;
}
这个方法虽然空间复杂度也是O(N)（递归栈），但代码很巧妙。
3 的幂
与2的幂类似。
解法一：循环除法
while (n % 3 == 0) { n /= 3; }
解法二：换底公式
log3(n) = log10(n) / log10(3)。判断这个结果是不是整数。
public boolean isPowerOfThree(int n) {
if (n <= 0) return false;
double logResult = Math.log10(n) / Math.log10(3);
// 检查是否为整数，注意精度问题
return (logResult - (int)logResult) < 1e-10;
}
解法三：整数限制法
int 范围内最大的 3 的幂是 3^19 = 1162261467。如果 n 是 3 的幂，它必然能整除这个数。
public boolean isPowerOfThree_math(int n) {
return n > 0 && 1162261467 % n == 0;
}
这个是最骚的。
有效的完全平方数
问题描述:
给定一个正整数
num，编写一个函数，如果num是一个完全平方数，则返回true，否则返回false。
解法一：暴力法
从 1 开始循环到 num，看 i*i 是否等于 num。太慢，会超时。
解法二：二分查找
在一个有序的范围内（1 到 num）找一个数 mid，使得 mid * mid == num。这是标准解法。
public boolean isPerfectSquare(int num) {
if (num < 1) return false;
if (num == 1) return true;
long left = 1, right = num; // 用long防止mid*mid溢出
while (left <= right) {
long mid = left + (right - left) / 2;
long square = mid * mid;
if (square == num) {
return true;
} else if (square < num) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
解法三：数学性质
完全平方数有个性质：1 + 3 + 5 + ... + (2n-1) = n^2。 我们可以从 num 里依次减去 1, 3, 5, ... 看最后是否能减到0。
public boolean isPerfectSquare_math(int num) {
int i = 1;
while (num > 0) {
num -= i;
i += 2;
}
return num == 0;
}
剩下两题比较冷门，简要说下思路。
三元表达式解析器
问题描述:
给定一个代表三元表达式的字符串，求出这个表达式的值。 ... (T?T?F:T:F) ...
思路： 从右往左找 ? 和 :。因为三元表达式是右结合的。用一个栈，遇到 ? 前的字母和 : 后的字母就入栈，遇到 ? 及其前面的 T/F，就弹栈决定取哪个，然后把结果再入栈。递归解法更清晰：parse(exp)，找到最外层的 ? 和与之匹配的 :，如果条件为 T，就递归 parse 第一个分支，否则递归 parse 第二个分支。
输出二叉树
问题描述:
在一个
m*n的二维字符串数组中输出二叉树。 ... (格式化输出)
思路： 这是个典型的双递归过程。
第一次遍历（DFS）：计算树的高度
height。计算二维数组尺寸：宽度是
2^height - 1，高度是height。第二次遍历（DFS）：填充数组。定义一个
fill(node, r, c, height)方法。r, c是当前节点要填入的位置。根节点在(0, (width-1)/2)。它的左孩子在(r+1, c - 2^(height-r-2))，右孩子在(r+1, c + 2^(height-r-2))。
二进制链表转整数
问题描述:
给你一个单链表的头节点
head，其中的节点要么是 0 要么是 1，代表一个二进制数。返回这个链表所代表的十进制值。
解法一：数组转换
遍历链表存到数组，再从数组转成十进制。空间O(N)。
解法二：迭代
遍历链表，维护一个 sum。每次 sum = sum * 2 + node.val。
public int getDecimalValue(ListNode head) {
int sum = 0;
ListNode curr = head;
while (curr != null) {
sum = sum * 2 + curr.val;
// 也可以用位运算: sum = (sum << 1) | curr.val;
curr = curr.next;
}
return sum;
}
解法三：递归
定义 dfs(node)，返回以node结尾的二进制值。这个不好直接得到全局和。更好的递归思路是定义一个全局sum，后序遍历链表，用一个全局power记录当前是2的几次方。但实现起来远不如迭代简洁。解法二就是最优解。