Chuoer47's Blog

Appearance

本文转载自力扣讨论区，作者：灵茶山艾府（endlesscheng）。 原文链接：https://leetcode.cn/circle/discuss/K0n2gO/

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

一、链表 ​

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

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

  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 模板（节点编号从 0 开始）：

py
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
java
class LcaBinaryLifting {
    private final int[] depth;
    private final long[] dis; // 如果是无权树（边权为 1），dis 可以去掉，用 depth 代替
    private final int[][] pa;

    public LcaBinaryLifting(int[][] edges) {
        int n = edges.length + 1;
        int m = 32 - Integer.numberOfLeadingZeros(n); // n 的二进制长度
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] e : edges) {
            // 如果题目的节点编号从 1 开始，改成 x=e[0]-1 和 y=e[1]-1
            int x = e[0], y = e[1], w = e[2];
            g[x].add(new int[]{y, w});
            g[y].add(new int[]{x, w});
        }

        depth = new int[n];
        dis = new long[n];
        pa = new int[m][n];

        dfs(g, 0, -1);

        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                int p = pa[i][x];
                pa[i + 1][x] = p < 0 ? -1 : pa[i][p];
            }
        }
    }

    private void dfs(List<int[]>[] g, int x, int fa) {
        pa[0][x] = fa;
        for (int[] e : g[x]) {
            int y = e[0];
            if (y != fa) {
                depth[y] = depth[x] + 1;
                dis[y] = dis[x] + e[1];
                dfs(g, y, x);
            }
        }
    }

    // 返回 node 的第 k 个祖先节点
    // 如果不存在，返回 -1
    public int getKthAncestor(int node, int k) {
        for (; k > 0 && node >= 0; k &= k - 1) {
            node = pa[Integer.numberOfTrailingZeros(k)][node];
        }
        return node;
    }

    // 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
    public int getLCA(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = y;
            y = x;
            x = tmp;
        }
        // 使 y 和 x 在同一深度
        y = getKthAncestor(y, depth[y] - depth[x]);
        if (y == x) {
            return x;
        }
        for (int i = pa.length - 1; i >= 0; i--) {
            int px = pa[i][x], py = pa[i][y];
            if (px != py) {
                x = px;
                y = py; // 同时往上跳 2^i 步
            }
        }
        return pa[0][x];
    }

    // 返回 x 到 y 的距离（最短路长度）
    public long getDis(int x, int y) {
        return dis[x] + dis[y] - dis[getLCA(x, y)] * 2;
    }
}
cpp
class LcaBinaryLifting {
    vector<int> depth;
    vector<long long> dis; // 如果是无权树（边权为 1），dis 可以去掉，用 depth 代替
    vector<vector<int>> pa;

public:
    LcaBinaryLifting(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        int m = bit_width((unsigned) n); // n 的二进制长度
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : edges) {
            // 如果题目的节点编号从 1 开始，改成 x=e[0]-1 和 y=e[1]-1
            int x = e[0], y = e[1], w = e[2];
            g[x].emplace_back(y, w);
            g[y].emplace_back(x, w);
        }

        depth.resize(n);
        dis.resize(n);
        pa.resize(m, vector<int>(n, -1));

        auto dfs = [&](this auto&& dfs, int x, int fa) -> void {
            pa[0][x] = fa;
            for (auto& [y, w] : g[x]) {
                if (y != fa) {
                    depth[y] = depth[x] + 1;
                    dis[y] = dis[x] + w;
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);

        for (int i = 0; i < m - 1; i++) {
            for (int x = 0; x < n; x++) {
                if (int p = pa[i][x]; p != -1) {
                    pa[i + 1][x] = pa[i][p];
                }
            }
        }
    }

    // 返回 node 的第 k 个祖先节点
    // 如果不存在，返回 -1
    int get_kth_ancestor(int node, int k) {
        for (; k > 0 && node >= 0; k &= k - 1) {
            node = pa[countr_zero((unsigned) k)][node];
        }
        return node;
    }

    // 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
    int get_lca(int x, int y) {
        if (depth[x] > depth[y]) {
            swap(x, y);
        }
        y = get_kth_ancestor(y, depth[y] - depth[x]); // 使 y 和 x 在同一深度
        if (y == x) {
            return x;
        }
        for (int i = pa.size() - 1; i >= 0; i--) {
            int px = pa[i][x], py = pa[i][y];
            if (px != py) {
                x = px;
                y = py; // 同时往上跳 2^i 步
            }
        }
        return pa[0][x];
    }

    // 返回 x 到 y 的距离（最短路长度）
    long long get_dis(int x, int y) {
        return dis[x] + dis[y] - dis[get_lca(x, y)] * 2;
    }
};
go
func minimumWeight(edges [][]int, queries [][]int) []int {
    n := len(edges) + 1
    type edge struct{ to, wt int }
    g := make([][]edge, n)
    for _, e := range edges {
        // 如果题目的节点编号从 1 开始，改成 x=e[0]-1 和 y=e[1]-1
        x, y, wt := e[0], e[1], e[2]
        g[x] = append(g[x], edge{y, wt})
        g[y] = append(g[y], edge{x, wt})
    }

    const mx = 17 // bits.Len(uint(n))
    pa := make([][mx]int, n)
    dep := make([]int, n)
    dis := make([]int, n) // 如果是无权树（边权为 1），dis 可以去掉，用 dep 代替

    var dfs func(int, int)
    dfs = func(x, p int) {
        pa[x][0] = p
        for _, e := range g[x] {
            y := e.to
            if y == p {
                continue
            }
            dep[y] = dep[x] + 1
            dis[y] = dis[x] + e.wt
            dfs(y, x)
        }
    }
    dfs(0, -1)

    for i := range mx - 1 {
        for x := range pa {
            p := pa[x][i]
            if p != -1 {
                pa[x][i+1] = pa[p][i]
            } else {
                pa[x][i+1] = -1
            }
        }
    }

    uptoDep := func(x, d int) int {
        for k := uint32(dep[x] - d); k > 0; k &= k - 1 {
            x = pa[x][bits.TrailingZeros32(k)]
        }
        return x
    }

    // 返回 x 和 y 的最近公共祖先（节点编号从 0 开始）
    getLCA := func(x, y int) int {
        if dep[x] > dep[y] {
            x, y = y, x
        }
        y = uptoDep(y, dep[x]) // 使 y 和 x 在同一深度
        if y == x {
            return x
        }
        for i := mx - 1; i >= 0; i-- {
            px, py := pa[x][i], pa[y][i]
            if px != py {
                x, y = px, py // 同时往上跳 2^i 步
            }
        }
        return pa[x][0]
    }

    // 返回 x 到 y 的距离（最短路长度）
    getDis := func(x, y int) int { return dis[x] + dis[y] - dis[getLCA(x, y)]*2 }

    // 以上是 LCA 模板

    ans := make([]int, len(queries))
    for i, q := range queries {
        // ...
    }
    return ans
}

数组上的倍增：

§3.9 虚树 ​

§3.10 树上启发式合并 ​

§3.11 点分治 ​

§3.12 树上滑动窗口 ​

§3.13 其他 ​

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

四、回溯 ​

本质是搜索树上的 DFS。

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

§4.1 入门回溯 ​

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

§4.2 子集型回溯 ​

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

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

也可以用二进制枚举做。

思维扩展：

§4.3 划分型回溯 ​

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

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

§4.4 组合型回溯 ​

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

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

§4.5 排列型回溯 ​

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

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

§4.6 有重复元素的回溯 ​

§4.7 搜索 ​

§4.8 折半枚举 ​

英文名 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站@灵茶山艾府

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