• 灵神关于图论的题单：图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）

• 模拟退火：刷题交流｜【模拟退火算法】求解经典的地图填色问题

• 自己对二叉树的了解：对二叉树的简单了解

• 可视化面板：算法可视化速查页

• Online Compiler：Online Compiler, AI Tutor, and Visual Debugger for Python, Java, C, C++, and JavaScript

一、基础遍历

思考：

• 如何思考递归？（不要一来就看细节，将原问题划分成子问题）
• 为什么需要使用递归？
• 为什么递归是对的？（数学归纳法，当n=1时成立；假设n=m...）
• 计算机是怎么执行递归过程的？（通过压栈和出栈实现递归）

问：一直有个疑问，啥时候需要有返回值，啥时候不需要返回值？

• 看你怎么写递归，如果是自顶向下的话，可以没有返回值；如果是自底向上的话，就一定要有返回值。

思考结果：

• 我们在循环的时候，就是在重复的执行同样一份代码；我们将原问题划分成相同的子问题，在计划原问题和子问题的时候应该也使用同样一套代码
• 将原问题划分成更小的子问题，再把更小的子问题划分成在小的子问题，这个过程就是递归中的递，不断递下去，总会有尽头，就是递归的边界条件。
• 从递归的边界条件返回的时候，就是递归中的归。非边界条件。
• 在递归的时候，除了把节点传下去，还可以把路径上的节点个数也传下去。

• 递归怎么知道return到那个节点上呢？在递归的时候，计算机没有丢弃上一个节点，而是保存下来了，那用什么数据结构存储呢？用栈存储，递归的递就是压栈的过程，递归的归就是出栈的过程。

学习 labuladong 关于图相关的理论和知识点。

图的话和多叉树遍历类似，需要防止遍历的时候形成环，使用数据 visit 来表示每个节点是否被访问过。

图的存储的话有两种方式，一个是领接表，一个是领接矩阵，分别定义如下：

// 邻接表
List<Integer>[] graph;

// 邻接矩阵
boolean[][] graph;

如果是带权图的话，邻接表存储的时候顺便把权重也存起来，邻接矩阵的话，每个坐标存的就是权重，不是 true 或者 false。

度（degree），入度（indegree）， 出度（outdegree）

矩阵（martix），顶点（vertex）

图的遍历模版：

// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;

void traverse(Graph graph, int s){
  if(visited[s]){
    return;
  }
  //  经过节点s，标记为已遍历
  visited[s] = true;
  // 做选择：标记节点s在路径上
  onPath[s] = true;
  for(int neighbor: graph.neighors(s)){
    traverse(graph, neighbor);
  }
  // 撤销选择，节点s离开路径
  onPath[s] = false;
}

1.1、DFS基础

547. 省份数量（20250723）⭐️

这个题就是求无向图中的连通域的个数，直接 dfs/bfs。

DFS

class Solution {
    public int findCircleNum(int[][] isConnected) {
        //求图联通区域的个数
        int n = isConnected.length;
        int ans = 0;
        boolean[] visited = new boolean[n];
        for(int i=0;i<n;i++){
            if(!visited[i]){  // 没有被访问的时候才调用dfs
                ans++;
                dfs(i, isConnected, visited);
            }
        }
        return ans;
    }

    public void dfs(int i, int[][]isConnected, boolean[] visited){
        visited[i] = true;
        for(int j  =0;j<isConnected.length;j++){
            //
            if(isConnected[i][j] == 1 && !visited[j]){
                dfs(j, isConnected, visited);
            }
        }
    }
}

BFS

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        int cnt = 0;
        Queue<Integer> queue = new LinkedList<>();
        for(int i =0;i<n;i++){
            if(!visited[i]){
                cnt++;
                queue.offer(i);
                visited[i] = true;
                while(!queue.isEmpty()){
                    int v = queue.poll();
                    for(int w=0;w<n;w++){
                        if(isConnected[v][w] == 1 && !visited[w]){
                            visited[w] = true;
                            queue.offer(w);
                        }
                    }
                }
            }
        }
        return cnt;
    }
}

并差集

class Solution {
    public int findCircleNum(int[][] isConnected) {

        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.size;
    }

}

class UnionFind {
    int[] roots;
    int size;// 连通图的个数

    public UnionFind(int n) {
        roots = new int[n];
        size = n;
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }
    }

    public int find(int i) {
        if (i == roots[i]) {
            return i;
        }
        roots[i] = find(roots[i]);
        return roots[i];
    }

    public void union(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);
        if (xroot == yroot) {
            return;
        }
        roots[yroot] = xroot;
        size--;
    }
}

题目给出的 isConnected 是邻接矩阵的存储方式。

···

404. 左叶子之和（20250327）

只有从左节点回到根节点的时候，我们才能确认是左节点，这个时候同时在判断是否是叶子节点（左右节点都为空）就可以了。

java

class Solution {
    int ans = 0;

    public int sumOfLeftLeaves(TreeNode root) {
        // 题目求的是左叶子之和，强调的是所有叶子节点的左叶子节点
        // 不是左叶子之和，不是左节点之和
        dfs(root);
        return ans;
    }

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
      	// 判断是不是叶子节点，判断是不是左节点
        if (root.left != null && root.left.left == null && root.left.right == null) {
            ans += root.left.val;
        }
        dfs(root.left);
        dfs(root.right);
    }
}

实现力扣树构建的方式，比如给出[1,2,3,4,5], [3,9,20,null,null,15,7] 能够知道是一颗什么样子的树。

543. 二叉树的直径（20250327）

二叉树的直径就是任意两个节点的最大路径，我们只需要求到根节点左子树的最大高度，加上右子树的最大高度再加一就是我们需要的结果。

java

class Solution {
    int mx = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        // 左节点的最大高度+右节点的最大高度
        dfs(root);
        return mx;
    }

    int dfs(TreeNode root) {
        // 这个函数是求一个节点的最大高度
        if (root == null) {
            return 0;
        }
        // 左右子树的最大高度
        int lv = dfs(root.left);
        int rv = dfs(root.right);
        mx = Math.max(mx, lv + rv);
        // 这个怎么理解？因为左右子树的最大高度是没有加上根节点的。
        return 1 + Math.max(lv, rv);
    }
}

114. 二叉树展开为链表（20250328）

labuladong算法可视化面板

Java

class Solution {
    public void flatten(TreeNode root) {
        dfs(root);
    }

    void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        // 遍历节点的左右子树
        dfs(root.left);
        dfs(root.right);
        // 将左节点放到右节点的位置，然后把右节点放到刚才左子树的右节点上
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = null;
        root.right = left;  
        // 需要定义一个p用来遍历roo提的有子树
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
}

116. 填充每个节点的下一个右侧节点指针（20250328）

traver(l.left, l.right), traver(r.left, r.right), traver(l.right, r.left) ???

Java

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        traver(root.left, root.right);
        return root;
    }
    void traver(Node l, Node r) {
        if (l == null || r == null) {
            return;
        }
        l.next = r;
        traver(l.left, l.right);
        traver(r.left, r.right);
        traver(l.right, r.left);
    }
}

112. 路径总和（20250329）

给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标targetSum。如果存在，返回true；否则，返回false。

自顶向下的DFS方法求解路径总和

129. 求根节点到叶节点数字之和（20250329）

给你一个二叉树的根节点root，树中每个节点都存放一个0-9的数字，每条从根到叶子节点的路径代表一个数字：

• 例如，从根节点到叶子节点的路径1-2-3表示数字123.

计算从根节点到叶子节点生成的所有数字之和。

自顶向下的深度遍历解决《求根节点到叶子节点数字之和》

1448. 统计二叉树中好节点的数目（20250329）

给你一颗根为root的二叉树，请你返回二叉树中好节点的数目。

好节点X定义为：从根节点到节点X所经过的节点中，没有任何节点的值大雨X的值。

灵神-自顶向下

class Solution {
    int cnt = 0;
    public int goodNodes(TreeNode root) {
        // 因为有负数，这里mx默认不能传0
        dfs(root, root.val);
        return cnt;
    }
    // mx 节点之前的最大的值
    void dfs(TreeNode root, int mx) {
        if (root == null) {
            return;
        }
        if (root.val >= mx) {
            cnt++;
        }
        mx = Math.max(mx, root.val);
        dfs(root.left, mx);
        dfs(root.right, mx);
    }
}

灵神-自底向上

/**
* 向下递归的时候，维护一个参数mx，表示从根节点到当前节点之前，路径上最大的节点值
* 如果当前节点为空，到达递归边界，返回0
* 递归左子树，获取左子树的好节点个数left
* 递归右子树，获取右子树的好节点个数right
* 如果当前节点是好节点，即root.val >= mx，那么返回left+right+1, 否则返回left+right
*/
class Solution {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }

    // 思考如何使用自底向上的方式求解？
    int dfs(TreeNode root, int mx) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left, Math.max(mx, root.val));
        int right = dfs(root.right, Math.max(mx, root.val));
        // 这里相当于在返回节点的时候，去判断是否是好节点
        // 相当于他从上往下对每个节点维护了一个mx值，这个值就是从根节点到当前节点的最大值。
        return left + right + (mx <= root.val ? 1 : 0);
    }
}

236. 二叉树的最近公共祖先（20250404）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

什么是节点的祖先？比如节点0的话，他的祖先就有2，6两个节点；比如节点3，那么他的祖先就有4，2，6三个节点。

求两个节点的最近公共祖先？

Java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        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) {
            return root;
        }
        if (left != null) {
            return left;
        }
        return right;
    }
}

235. 二叉搜索树的最近公共祖先（20250404）

二叉搜索树的特点就是，节点的左子树的值都是小于节点的值，节点的右子树都是大于节点的值。

我们可以通过节点的值来判断p和q的位置关系。

Java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int x = root.val;
        if(p.val < x && q.val < x){
            return lowestCommonAncestor(root.left, p, q);
        }
        if(p.val > x && q.val > x){
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}

1.2、BFS基础

求最短路径，要求边权都是 1 （或者说都是同一个正数）

模版（单源最短路）

public class BFS {

    public int[] bfs(int n, int[][] edges, int start) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, x -> new ArrayList<>());

        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            g[x].add(y);
            g[y].add(x);
        }

        // 定义一个数组表示从起点到终点的距离
        int[] dis = new int[n];
        // 表示尚未访问
        Arrays.fill(dis, -1);
        // 定义一个队列
        Queue<Integer> q = new ArrayDeque<>();
        // 起点距离起点为0
        dis[start] = 0;
        // 把起点放到队列里面
        q.offer(start);

        // bfs老套路
        while (!q.isEmpty()) {
            int x = q.poll();
            // 循环处理相联的所有节点。
            for (int y : g[x]) {
                if (dis[y] < 0) {
                    dis[y] = dis[x] + 1;
                    q.offer(y);
                }
            }
        }
        return dis;
    }
}

···

1791. 找出星型图的中心节点

有一个无向的星型图，由 n 个编号从 1 到 n 的节点组成，星型图有一个中心节点，并且恰有 n-1 条边将中心节点与其他节点连接起来。

给你一个二维整数数组 edges，其中 edges[i]=[ui, vi]表示在节点之间存在一条边，请你找出返回 edges 所有表示星型图的中心节点。

根据题意，中心节点必然出现在所有的 edges[i]中，根据第一条边，判断里面的两个数据是否在后面边里面，如果在的话，就是中心节点，否则就不是中心节点。

因为题目给出 n 是大于等于 3 的，必定是大于两个节点的。

class Solution {
    public int findCenter(int[][] edges) {
        int a = edges[0][0], b =edges[0][1];
        if(a == edges[1][0] || a == edges[1][1]){
            return a;
        }
        else{
            return b;
        }
    }
}

1557. 可以到达所有点的最少点数目

给你一个 有向无环图， n 个节点编码为 0 到 n-1， 以及一个变数组 edges，其中 edges[i] = [from, to], 表示一条从 from 到 to 的有向边。

找到最小的点集使得从这些点出发能到达图中所有的点，题目保证解存在且唯一。

你可以以任何顺序返回这些节点的编号。

最小的点集使得能够到达图的所有点，这里我们只需要找到入度为 0 的节点就是题目的解。

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        // 只有出度没有入度的节点?
        int[] ans = new int[n];

        for(List<Integer> dt: edges){
            ans[dt.get(1)] += 1;
        }
        List<Integer> res = new ArrayList<>();
        for(int i=0;i<ans.length;i++){
            if(ans[i] == 0){
                res.add(i);
            }
        }
        return res;
    }
}

构建 java 列表并初始化的方式

1、List<Integer> list = Arrays.asList(1,2,3);

2、List<Integer> lit = new ArrayList<>(Arrays.asList(1,1,3));

3、List<String> lit = new ArrayList<>(Collections.singletonList("a", "b"));

LCR 110. 所有可能的路径

给定一个有 n 个节点的有向无环图，用二维数组 graph 表示，请找到所有从 0 到 n-1 的路径并输出。

graph 的第 i 个数组中的单元都表示有向图 i 号节点所能够到达的下一个节点。

从 0 节点开始遍历图，将到达 n-1 的路径保存下来。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 无环图
        // 从 0 到 n-1的所有路径
        // graph 邻接表
        List<Integer> onPath = new ArrayList<>();
        traverse(graph, 0, onPath);
        return res;
    }
    // s 表示节点
    public void traverse(int[][] graph, int s, List<Integer> onPath){
        onPath.addLast(s);
        int n  = graph.length;
        if(s == n-1){
            res.add(new ArrayList<>(onPath));
        }
        for(int v: graph[s]){  // graph[s] 表示s能到达的所有节点
            traverse(graph, v, onPath);
        }
        onPath.removeLast();
    }
}

3243. 新增道路查询后的最短距离 I（20250804）

Details

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。

queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。

返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

示例 1：

输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]

输出： [3, 2, 1]

解释：

新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。

新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。

新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。

示例 2：

输入： n = 4, queries = [[0, 3], [0, 2]]

输出： [1, 1]

解释：

新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。

新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。

提示：

• 3 <= n <= 500
• 1 <= queries.length <= 500
• queries[i].length == 2
• 0 <= queries[i][0] < queries[i][1] < n
• 1 < queries[i][1] - queries[i][0]
• 查询中没有重复的道路。

大致的意思就是，给出n个点，每个点i都有一个同向点i+1的路径（i == n除外），每次添加一条路径，求添加之后从0到达n-1的最短路径是多少。

直接每次添加之后，都BFS搜索一遍求答案。

Java

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        // 求0到n-1的最短距离
        List < Integer > [] g = new ArrayList[n];
        Arrays.setAll(g, x -> new ArrayList < > ());
        for (int i = 0; i < n - 1; i++) {
            g[i].add(i + 1);
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] row = queries[i];
            int x = row[0], y = row[1];
            g[x].add(y);
            ans[i] = bfs(g, n);
        }
        return ans;
    }

    public int bfs(List < Integer > [] g, int n) {
        // 遍历从i到j的最短路径
        int[] dis = new int[n];
        // 先填充值，在设置默认值。
        Arrays.fill(dis, -1);
        dis[0] = 0;
        Deque < Integer > q = new ArrayDeque < > ();
        q.offer(0);
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int y: g[x]) {
                if (dis[y] < 0) {
                    dis[y] = dis[x] + 1;
                    q.offer(y);
                }
            }
        }
        return dis[n - 1];
    }
}

二、拓扑排序

把拓扑排序想象成一个黑盒，给它一堆杂乱的先修约束，它会给你一个井井有条的课程学习安排。

这一种在图上排序，可以把杂乱的点排成一排，前提条件是图中没有环，从而保证每条边都从排在前面的点，指向排在后面的点，即对于任意向边$x->y$，x一定在y前面。

2.1 拓扑排序

模版

public class Solution {

    // 返回有向无环图（DAG）的其中一个拓扑序
    // 如果图中有环，返回空列表
    // 节点编号从0到n-1

    public List<Integer> topologicSort(int n, int[][] edges) {
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, x -> new ArrayList<>());
        int[] inDeg = new int[n];

        for (int[] e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            // 统计y的先修课数量
            inDeg[y]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 没有先修课，可以直接上
            if (inDeg[i] == 0) {
                q.offer(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!q.isEmpty()) {
            int x = q.poll();
            topoOrder.add(x);

            for (int y : g[x]) {
                inDeg[y]--;
                if (inDeg[y] == 0) {
                    q.offer(y);
                }
            }
        }
        // 表示图中有环
        if (topoOrder.size() < n) {
            return Collections.emptyList();
        }
        return topoOrder;
    }
}

210. 课程表 II（20250811）

Details

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• 所有[ai, bi] 互不相同

简单来说，就是给出一个数据[ai, bi]，表示要修ai课程之前，必须修bi课程，返回修完所有课程的顺序。

首先需要找到那些入度为0的所有节点，这些节点需要首先访问，然后广度遍历，将遍历的结果存入到返回的数据结构中。

• 返回空数据可以用 new int[0];

Java

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {

        List<Integer>[] g = new ArrayList[numCourses];
        Arrays.setAll(g, x -> new ArrayList<>());
        // 每个节点的入度数据
        int[] inDeg = new int[numCourses];

        for (int[] e : prerequisites) {
            int x = e[0], y = e[1];
            g[y].add(x);
            inDeg[x]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDeg[i] == 0) {
                q.offer(i);
            }
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!q.isEmpty()) {
            int x = q.poll();
            topoOrder.add(x);

            // 与x相联的每一条边
            for (int y : g[x]) {
                inDeg[y]--;
                if (inDeg[y] == 0) {
                    q.offer(y);
                }
            }
        }
        if (topoOrder.size() < numCourses) {
            return new int[0];
        }
        return topoOrder.stream().mapToInt(x -> x).toArray();
    }
}

2.2 在拓扑序上 DP

2.3 基环树

三、最短路

3.1 单源最短路：Dijkstra 算法

3.2 全源最短路：Floyd 算法

四、最小生成树

五、欧拉路径/欧拉回路

六、强连通分量/双连通分量

七、二分图染色

八、网络流

九、其他

Changelog

8/20/25, 11:06 AM

View All Changelog

• 4c155-Merge branch 'dev1'on 8/20/25