分享丨【算法题单】链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
灵茶山艾府
418946
发布于 浙江
树深度优先搜索广度优先搜索二叉搜索树递归链表二叉树C++JavaPythonPython3周赛双周赛学习分享

链表题单 二叉树题单 链表题目 二叉树题目 回溯题单 回溯题目 灵茶山艾府 灵神 灵神题单

一、链表

注：由于周赛中的链表题可以转成数组处理，难度比直接处理链表低，故不标明难度分。

带着问题去做下面的题目：

  1. 在什么情况下，要用到哨兵节点（dummy node）？
  2. 在什么情况下，循环条件要写 while (node != null)？什么情况下要写 while (node.next != null)？

§1.1 遍历链表

§1.2 删除节点

视频讲解【基础算法精讲 08】

思维扩展：

§1.3 插入节点

§1.4 反转链表

视频讲解【基础算法精讲 06】

§1.5 前后指针

视频讲解【基础算法精讲 08】

§1.6 快慢指针

视频讲解【基础算法精讲 07】

思维扩展：

§1.7 双指针

§1.8 合并链表

§1.9 分治

§1.10 综合应用

§1.11 其他

二、二叉树

DFS BFS

学习递归，从二叉树开始。

晕递归的同学，请先看视频讲解【基础算法精讲 09】，欢迎点赞~

一般有三种遍历方式：

  • 先序遍历：见 §2.2 自顶向下 DFS。
  • 中序遍历：见 §2.9 二叉搜索树。
  • 后序遍历：见 §2.3 自底向上 DFS。

带着问题去做下面的题目：

  1. 一般来说，DFS 的递归边界是空节点。在什么情况下，要额外把叶子节点作为递归边界？
  2. 在什么情况下，DFS 需要有返回值？什么情况下不需要有返回值？
  3. 在什么情况下，题目更适合用自顶向下的方法解决？什么情况下更适合用自底向上的方法解决？

§2.1 遍历二叉树

§2.2 自顶向下 DFS（先序遍历）

在「递」的过程中维护值。

有些题目自顶向下和自底向上都可以做。有些题目也可以用 BFS 做。

§2.3 自底向上 DFS（后序遍历）

在「归」的过程中计算。

如何灵活运用递归？【基础算法精讲 10】

§2.4 自底向上 DFS：删点

§2.5 有递有归

§2.6 二叉树的直径

视频讲解【基础算法精讲 23】

另见本题单的「§3.5 树的直径」。

§2.7 回溯

§2.8 最近公共祖先

视频讲解【基础算法精讲 12】

§2.9 二叉搜索树

一般是中序遍历。

视频讲解【基础算法精讲 11】

§2.10 创建二叉树

§2.11 插入/删除节点

§2.12 树形 DP

更多树形 DP，见 动态规划题单 的「十二、树形 DP」。

§2.13 二叉树 BFS

视频讲解【基础算法精讲 13】

§2.14 链表+二叉树

§2.15 N 叉树

§2.16 其他

三、一般树

§3.1 遍历

§3.2 自顶向下 DFS

§3.3 自底向上 DFS

§3.4 有递有归

§3.5 树的直径

视频讲解【基础算法精讲 23】

§3.6 树的拓扑排序

§3.7 DFS 时间戳

可以把树上问题转化成数组问题，比如子树的操作转化成子数组的操作。通常要结合其他数据结构。

§3.8 最近公共祖先（LCA）、倍增算法

讲解

带权树 LCA 模板（节点编号从 开始）：

Python3
Java
C++
Go
class LcaBinaryLifting:
    def __init__(self, edges: List[List[int]]):
        n = len(edges) + 1
        m = n.bit_length()
        g = [[] for _ in range(n)]
        for x, y, w in edges:
            # 如果题目的节点编号从 1 开始，改成 x-1 和 y-1
            g[x].append((y, w))
            g[y].append((x, w))

        depth = [0] * n
        dis = [0] * n  # 如果是无权树（边权为 1），dis 可以去掉，用 depth 代替
        pa = [[-1] * n for _ in range(m)]

        def dfs(x: int, fa: int) -> None:
            pa[0][x] = fa
            for y, w in g[x]:
                if y != fa:
                    depth[y] = depth[x] + 1
                    dis[y] = dis[x] + w
                    dfs(y, x)
        dfs(0, -1)

        for i in range(m - 1):
            for x in range(n):
                if (p := pa[i][x]) != -1:
                    pa[i + 1][x] = pa[i][p]

        self.depth = depth
        self.dis = dis
        self.pa = pa

    # 返回 node 的第 k 个祖先节点
    # 如果不存在，返回 -1
    def get_kth_ancestor(self, node: int, k: int) -> int:
        pa = self.pa
        for i in range(k.bit_length()):
            if k >> i & 1:
                node = pa[i][node]
                if node < 0: 
                    return -1
        return node

    # 返回 x 和 y 的最近公共祖先
    def get_lca(self, x: int, y: int) -> int:
        if self.depth[x] > self.depth[y]:
            x, y = y, x
        # 使 y 和 x 在同一深度
        y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])
        if y == x:
            return x
        pa = self.pa
        for i in range(len(pa) - 1, -1, -1):
            px, py = pa[i][x], pa[i][y]
            if px != py:
                x, y = px, py  # 同时往上跳 2**i 步
        return pa[0][x]

    # 返回 x 到 y 的距离（最短路长度）
    def get_dis(self, x: int, y: int) -> int:
        return self.dis[x] + self.dis[y] - self.dis[self.get_lca(x, y)] * 2

数组上的倍增：

§3.9 虚树

§3.10 树上启发式合并

§3.11 点分治

§3.12 树上滑动窗口

§3.13 其他

另见 动态规划题单 的「十二、树形 DP」，包含换根 DP。

四、回溯

本质是搜索树上的 DFS。

推荐先完成本题单的 §2.7 节，先理解二叉树上的回溯，再来学习一般情况下的回溯。

§4.1 子集型回溯

视频讲解【基础算法精讲 14】

有「选或不选」和「枚举选哪个」两种写法。

也可以用二进制枚举做。

思维扩展：

§4.2 划分型回溯

视频讲解【基础算法精讲 14】

把分割线（逗号）看成是可以「选或不选」的东西，本质是子集型回溯。

§4.3 组合型回溯

视频讲解【基础算法精讲 15】

有个数上的约束。也算作子集型回溯。

§4.4 排列型回溯

视频讲解【基础算法精讲 16】

部分题目也可以用状压 DP 做。

§4.5 有重复元素的回溯

§4.6 搜索

§4.7 折半搜索

英文名 meet in the middle。

讲解（见文末）

五、其他递归/分治

手写快排：

算法题单

如何科学刷题？

  1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
  2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
  3. 单调栈（基础/矩形面积/贡献法/最小字典序）
  4. 网格图（DFS/BFS/综合应用）
  5. 位运算（基础/性质/拆位/试填/恒等式/思维）
  6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
  7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
  8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
  9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
  10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
  11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
  12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

如果你发现有题目可以补充进来，欢迎评论反馈。

评论 (157)