Typescript-Algorithms
    Preparing search index...

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

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

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

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

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

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

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

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

    思维扩展：

    DFS BFS

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

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

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

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

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

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

    在「归」的过程中计算。

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

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

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

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

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

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

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

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

    讲解

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

    Python3

    Java

    C++

    Go

    class LcaBinaryLifting:
    def __init__(self, edges: List[List[int]]):
        n = len(edges) + 1
        self.m = m = n.bit_length()
        g = [[] for _ in range(n)]
        for x, y, w in edges:
            g[x].append((y, w))
            g[y].append((x, w))

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

        def dfs(x: int, fa: int) -> None:
            pa[x][0] = 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[x][i]) != -1:
                    pa[x][i + 1] = pa[p][i]

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

    def get_kth_ancestor(self, node: int, k: int) -> int:
        for i in range(k.bit_length()):
            if k >> i & 1:
                node = self.pa[node][i]
        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
        for i in range(self.m - 1, -1, -1):
            px, py = self.pa[x][i], self.pa[y][i]
            if px != py:
                x, y = px, py  # 同时往上跳 2**i 步
        return self.pa[x][0]

    # 返回 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

    数组上的倍增：

    另见 动态规划题单 中的「树形 DP」。

    本质是搜索树上的 DFS。

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

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

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

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

    也可以用二进制枚举做。

    思维扩展：

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

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

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

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

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

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

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

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

    Settings

    Member Visibility

    On This Page

    一、链表二、二叉树三、一般树四、回溯五、其他递归/分治算法题单