十一、链表、二叉树与回溯
分享丨【题单】链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
一、链表
1.1、遍历链表
21. 合并两个有序链表
leetcode 第 21 题，合并两个升序的链表，用一个虚拟节点和两个移动指针来解决，判断指针处的节点的大小，插入到虚拟节点后方
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 虚拟头结点
ListNode dummy = new ListNode(-1), p = dummy;
ListNode p1 = list1, p2 = list2;
while(p1!=null && p2 !=null){
if(p1.val > p2.val){
p.next = p2;
p2 = p2.next;
}
else{
p.next = p1;
p1 = p1.next; // 指针往后移动一位
}
p = p.next; // 移动p
}
// 添加上后面没有循环完的节点
if(p1!=null){
p.next = p1;
}
if(p2!=null){
p.next = p2;
}
return dummy.next;
}
}86.分割链表
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(-1); // 两个虚拟头结点
ListNode dummy2 = new ListNode(-1);
ListNode p1 = dummy1, p2 = dummy2; // 两个可移动的节点
ListNode p = head;
while(p != null){
if(p.val >= x){ // 判断节点值的大小，放到对应链表节点后面
p2.next = p;
p2 = p2.next;
}
else{
p1.next = p;
p1 = p1.next;
}
ListNode tmp = p.next; // 原链表指针移动
p.next = null;
p = tmp;
}
// 合并两个链表
p1.next = dummy2.next; // 链接两个链表
return dummy1.next; // 返回链表。
}
}23. 合并 K 个升序链表
这里用到一个二叉堆的数据结构， 先明白如何用，再说是怎样实现的， 就是使用一个优先级队列来处理，先把条件给出来的链表放到优先级队列里面，后面每次在 pull 出来最小的节点，放到虚拟节点的后面。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0){
return null;
}
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val) // a.val - b.val 最小堆
);
// put ListNode head in priorityQueue
for(ListNode head: lists){
if(head!= null){ // if head != null
pq.add(head);
}
}
while(!pq.isEmpty()){ // pq is not empty, pull minest node
ListNode node = pq.poll();
p.next = node;
if(node.next!=null){
pq.add(node.next);
}
p = p.next;
}
return dummy.next;
}
}二、二叉树
2.7、回溯
257. 二叉树的所有路径（20250405）
给你一个二叉树的根节点
root，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。
自顶向下递归求解
class Solution {
List<String> ans = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, "");
return ans;
}
// 通过递归求解
void dfs(TreeNode node, String path) {
if (node == null) {
return;
}
path += node.val; // 自顶向下递归，每次进入节点就添加到路径里面
if (node.left == node.right) { // 判断叶子节点
ans.add(path);
}
path += "->"; // 最后在用->关联
dfs(node.left, path);
dfs(node.right, path);
}
}回溯
class Solution {
List<String> ans = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
List<String> path = new ArrayList<>();
dfs(root, path);
return ans;
}
// 递归回溯解
void dfs(TreeNode node, List<String> path) {
if (node == null) {
return;
}
path.add(String.valueOf(node.val));
if (node.left == node.right) {
ans.add(String.join("->", path));
} else {
dfs(node.left, path);
dfs(node.right, path);
}
path.remove(path.size() - 1);
}
}可能你会问，什么时候使用递归？什么时候使用回溯？
递归是一个函数不断调用自身，通常用于把大问题拆解成小问题并逐步求解；回溯是在递归的基础上，尝试所有可能的解，并在不满足条件是回退，撤销上一步决策。
四、回溯
4.1、入门回溯
17. 电话号码的字母组合（20250405）
给定一个仅包含数字
2-9的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
用一个path数组记录路径上的字母。
回溯三问：
- 当前操作？枚举path[i]要填入的字母
- 子问题？构造字符串>=i的部分
- 下一个子问题？构造字符串>=i+1的部分
Java
class Solution {
static final String[] MAPPING = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
List<String> ans = new ArrayList<>();
char[] digits;
char[] path;
public List<String> letterCombinations(String digits) {
int n = digits.length();
if (n == 0) {
return List.of();
}
this.digits = digits.toCharArray();
path = new char[n];
dfs(0);
return ans;
}
void dfs(int i) {
// 递归边界
if (i == digits.length) {
ans.add(new String(path));
return;
}
// 枚举第i个字母是什么
for (char c : MAPPING[digits[i] - '0'].toCharArray()) {
path[i] = c;
dfs(i + 1);
}
}
}4.2、子集型回溯
有【选或者不选】和【枚举选那个】两种写法。
也可以用二进制枚举做。
78. 子集（20250405更新）
给你一个整数数组
nums，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
方法一：输入的视角（选或者不选）
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0);
return ans;
}
// 从输入的角度来解（就是选与不选的却别）
void dfs(int i) {
// 递归边界条件
if (i == nums.length) {
ans.add(new ArrayList<>(path));
return;
}
// 不选
dfs(i + 1);
// 选
path.add(nums[i]);
dfs(i + 1);
path.remove(path.size() - 1);
}
}方法二：答案的视角（枚举选哪个）
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0);
return ans;
}
void dfs(int i) {
// 由于子集的长度没有约束，所以每个长度都可以是答案，所以每次递归都需要记录一下答案
ans.add(new ArrayList<>(path));
if (i == nums.length) {
return;
}
// 枚举答案的第一个数选谁，第二个数选谁？
for (int j = i; j < nums.length; j++) {
path.add(nums[j]);
dfs(j + 1);
path.remove(path.size() - 1);
}
}
}Changelog
5/7/25, 10:15 AM
View All Changelog
8c7c5-on